Method for fast quotient guess and congruencies manipulation
View Patent ↗A processor-executed computational method especially for use in cryptographic systems quickly determines a polynomial quotient under specific conditions. For a polynomial modulus f(x), a maximum degree for a polynomial i(x) to be reduced by this method is defined as the sum of the degree of f(x) and the difference d between the degrees of the two highest degree coefficients of f(x). Polynomials i(x) with degree less than this maximum can be divided by a^[deg(f(x))] instead of the full f(x) to quickly obtain the quotient value. With this quotient a residue value can be obtained, or optionally a random congruent value.
1. A fast quotient estimation method implemented in an electronic digital processing system for performing polynomial operations in a finite field, the method comprising:
(a) determining from a polynomial modulus f(x) a degree Deg[f(x)] of the modulus and a distance d between two largest degree coefficients of the modulus, a maximum degree MAX_DEG={Deg[f(x)]+d−1};
(b) receiving a polynomial i(x); and
(c) if a degree Deg[i(x)] of the received polynomial i(x) is less than or equal to MAX_DEG; then dividing i(x) by a Deg[f(x)] where a is an integer to obtain a polynomial quotient q(x)=i(x)/f(x).
2. The method of claim 1 , further comprising:
(d) multiplying the quotient q(x) by the modulus f(x) and subtracting from the received polynomial i(x) to obtain a residue value r(x)=i(x)−f(x)·q(x).
3. The method of claim 2 , wherein the finite field is a binary field and the subtraction in (d) is a bitwise XOR operation.
4. The method of claim 2 , wherein a random multiple of the polynomial modulus is added to the residue after (d).
5. The method of claim 1 , wherein a random polynomial of degree less than d is added to the quotient after (c) to obtain a modified quotient q′(x), then:
(d′) multiplying the modified quotient q′(x) by the modulus f(x) and subtracting from the received polynomial i(x) to obtain a random value congruent to i(x)mod f(x).
6. The method of claim 1 , wherein the finite field is a prime field with a prime number p>2, and wherein coefficients of the polynomials f(x), i(x) and q(x) are integers from 0 to p−1.
7. The method of claim 1 , wherein the method is executed in a cryptographic processor.
8. The method of claim 7 , wherein the method is performed as part of execution of a symmetric block cipher by said cryptographic processor.
9. A processor-readable medium storing a program executable by an electronic digital processing system, the program stored on said medium causing the electronic digital processing system to perform polynomial operations in a finite field, the polynomial operations executed by the system comprising:
(a) determining, from a polynomial modulus f(x), a degree Deg[f(x)] of the modulus and a distance d between two largest degree coefficients of the modulus, a maximum degree MAX_DEG={Deg[f(x)]+d−1);
(b) receiving a polynomial i(x); and
(c) if a degree Deg[i(x)] of the received polynomial i(x) is less than or equal to MAX_DEG, then dividing i(x) by a Deg[f(x)] where a is an integer to obtain a polynomial quotient q(x)=i(x)/f(x).
10. The processor-readable medium of claim 9 , wherein the program further causes the processing system to:
(d) multiply the quotient q(x) by the modulus f(x) and subtracting from the received polynomial i(x) to obtain a residue value r(x)=i(x)−f(x)·q(x).
11. The medium as set forth in claim 10 , wherein the finite field is a binary field and the subtraction in (d) is a bitwise XOR operation.
12. The medium as set forth in claim 10 , wherein the program further causes the processor to add a random multiple of the polynomial modulus to the residue after (d).
13. The medium as set forth in claim 9 , wherein the program further causes the processor to add a random polynomial of degree less than d to the quotient after (c) to obtain a modified quotient q′(x), then:
(d′) multiply the modified quotient q′(x) by the modulus f(x) and subtract from the received polynomial i(x) to obtain a random value congruent to i(x)mod f(x).
14. The medium as set forth in claim 9 , wherein the finite field is a prime field with a prime number p>2, and wherein coefficients of the polynomials f(x), i(x) and q(x) are integers from 0 to p−1.
15. The medium as set forth in claim 9 , wherein the polynomial operations are executed by a cryptographic processor reading said medium.
16. The medium of claim 15 , wherein the polynomial operations are performed as part of execution of a symmetric block cipher by said cryptographic processor.