Random generator of orthogonal matrices in finite fields
AssigneeNew York University in Abu Dhabi Corporation
InventorsLasha EPHREMIDZE, Ilya SPITKOVSKY
Life of this patent
Estimating the term…
Abstract
Systems and methods for generating n×n orthogonal matrices in the Galois field GF(q) that is highly efficient and can handle large values of n and q. This method is based on random selection. In addition, this method can be used to construct paraunitary filter banks over finite fields, in applications such as signal processing. This approach can be useful constructing orthogonal matrices that satisfy specific constraints, making it potentially valuable for applications in coding theory and encryption.
Claims17
A method of cryptography comprising:
- constructing an orthogonal matrix with elements from finite fields;
- and
- encoding information using the constructed orthogonal matrix.
A method of signal processing comprising:
- constructing an orthogonal matrix with elements from finite fields;
- and
- processing a signal with the orthogonal matrix.
11-14. (canceled)
A computer-implemented cryptography system comprising:
- one or more processors;
- a computer-readable, non-transitory storage medium comprising instructions that, when executed by the one or more processors, cause the one or more processors to:
- select, from a finite field having a predetermined number of elements, random coefficients for a plurality of polynomials;
- construct, based on the selected coefficients, a paraunitary polynomial matrix over the finite field by executing a modified Janashia-Lagvilava computational procedure that avoids inversion of an m×m matrix;
- and
- convert the paraunitary polynomial matrix into at least one orthogonal matrix over the finite field;
- and
- an encoder configured to apply the orthogonal matrix to input data so as to encrypt data generating encrypted output data, wherein the at least one orthogonal matrix satisfies Q*QT=I over the finite field;
- wherein the the one or more processors is further configured to perform, prior applying the orthogonal matrix, a selection of the orthogonal matrix from a plurality of candidate orthogonal matrices, including the at least one orthogonal matrix, generated according to one or more predetermined constraints.
Dependencies are inferred from the claim text.