System and method for efficient basis conversion

• US 8,086,656 B2
• Filed: 10/04/2007
• Issued: 12/27/2011
• Est. Priority Date: 03/12/1999
• Status: Expired due to Term

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Lambert, Robert J.
• Primary Examiner(s): Malzahn, David H
• Application Number:
  US11/867,594
• Publication Number:
  US 20080077645A1
• Time in Patent Office: 1,545 Days
• Field of Search: None
• US Class Current: 708/492
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 2207/7209 Calculation via subfield, i.e. the subfield being GF(q) with q a prime power, e.g. GF ((2**m)**n) via GF(2**m)
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10
• CPC Class Codes: H04L 9/08 Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords network architectures or network communication protocols for supporting key management in a packet data network H04L63/06
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes

Abstract

This invention describes a method for evaluating a polynomial in an extension field F_q^M, wherein the method comprises the steps of partitioning the polynomial into a plurality of parts, each part is comprised of smaller polynomials using a q^−th power operation in a field of characteristic q; and computing for each part components of q^−th powers from components of smaller powers. A further embodiment of the invention provides for a method of converting a field element represented in terms of a first basis to its representation in a second basis, comprising the steps of partitioning a polynomial, being a polynomial in the second basis, into a plurality of parts, wherein each part is comprised of smaller polynomials using a q^−th power operation in a field of characteristic q; evaluating the polynomial at a root thereof by computing for each part components of q^−th powers from components of smaller powers; and evaluating the field element at the root of the polynomial.

Claims

1. A computing device comprising an accumulator for evaluating a polynomial a(x) of a finite field of characteristic 2 at an element r, said polynomial a(x) having a degree and being equivalent to a sum of a plurality of components having respective coefficients a_k combined with corresponding values r^k, said device being configured to:

a) initialize said accumulator to zero;

b) obtain the values r^k for odd numbers k less than said degree;

c) for each even number k less than said degree and greater than 2 which is also an exponentiation of 2, if the coefficient a_k is a one, add r¹ to said accumulator and square said accumulator;

d) for all other even numbers k less than said degree, if the coefficient a_k is a one, add the value r<sup>k−

1</sup> to said accumulator and square said accumulator;

e) for each odd number k greater than zero, if the coefficient a_k is a one, add the corresponding value r^k to said accumulator;

f) for k=0, if the coefficient a₀ is a one, add the value r⁰ to said accumulator; and

g) output a final value in said accumulator representing a(r).

2. The computing device according to claim 1 wherein said values r^k are pre-computed and stored in a memory accessible by said computing device.

3. The computing device according to claim 1 wherein said values r^k are computed by said device.

4. A method for evaluating a polynomial a(x) of a finite field of characteristic 2 at an element r, said polynomial a(x) having a degree and being equivalent to a sum of a plurality of components having respective coefficients a_k combined with corresponding values r^k, said method comprising the steps of:

a) initializing an accumulator to zero;

b) obtaining the values r^k for odd numbers k less than said degree;

c) for each even number k less than said degree and greater than 2 which is also an exponentiation of 2, if the coefficient a_k is a one, adding r¹ to said accumulator and squaring said accumulator;

d) for all other even numbers k less than said degree, if the coefficient a_k is a one, adding the value r<sup>k−

1</sup> to said accumulator and squaring said accumulator;

e) for each odd number k greater than zero, if the coefficient a_k is a one, adding the corresponding value r^k to said accumulator;

f) for k=0, if the coefficient a₀ is a one, adding the value r⁰ to said accumulator; and

g) providing a final value from said accumulator to a cryptographic scheme representing a(r).

5. The method according to claim 4 wherein said values r^k are pre-computed and stored in a memory accessible by a computing device.

6. The method according to claim 4 wherein said values r^k are computed by a computing device during execution of said method.

7. A computer readable medium comprising computer executable instructions for evaluating a polynomial a(x) of a finite field of characteristic 2 at an element r, said polynomial a(x) having a degree and being equivalent to a sum of a plurality of components having respective coefficients a_k combined with corresponding values r^k, said computer executable instructions comprising instructions for:

a) initializing an accumulator to zero;

b) obtaining the values r^k for odd numbers k less than said degree;

for each even number k less than said degree and greater than 2 which is also an exponentiation of 2, if the coefficient a_k is a one, adding r¹ to said accumulator and squaring said accumulator;

c) for all other even numbers k less than said degree, if the coefficient a_k is a one, adding the value r<sup>k−

1</sup> to said accumulator and squaring said accumulator;

d) for each odd number k greater than zero, if the coefficient a_k is a one, adding the corresponding value r^k to said accumulator;

e) for k=0, if the coefficient a₀ is a one, adding the value r₀ to said accumulator; and

f) providing a final value from said accumulator to a cryptographic scheme representing a(r).

8. The computer readable medium according to claim 7 wherein said values r^k are pre-computed and stored in a memory accessible by a computing device.

9. The computer readable medium according to claim 7 wherein said values r^k are computed by a computing device during execution of said method.

10. A computer device comprising an accumulator for evaluating a polynomial a(x) of a finite field of characteristic 3 at an element r, said polynomial a(x) having a degree and being equivalent to a sum of a plurality of components having respective coefficients a_k combined with corresponding values r^k, said device being configured to:

a) initialize said accumulator to zero;

b) for each number k which is less than said degree and greater than 3, and which is an exponentiation of 3, in descending order, add the coefficient a_k multiplied by the value r¹ to said accumulator;

c) cube said accumulator;

d) obtain the values r^k for each number k which when multiplied by 3 a result is less than said degree and the result was not chosen in b);

e) for each number k from d), add the value r^k obtained in d) multiplied by the coefficient a_3k to said accumulator;

f) cube said accumulator;

g) for all remaining coefficients a_k, add the corresponding component a_k r^k to said accumulator; and

h) output a final value in said accumulator representing a(r).

11. The computing device according to claim 10 wherein said values r^k are pre-computed and stored in a memory accessible by said computing device.

12. The computing device according to claim 10 wherein said values r^k are computed by said device.

13. A method for evaluating a polynomial a(x) of a finite field of characteristic 3 at an element r, said polynomial a(x) having a degree and being equivalent to a sum of a plurality of components having respective coefficients a_k combined with corresponding values r^k, said method comprising the steps of:

a) initializing an accumulator to zero;

b) for each number k which is less than said degree and greater than 3, and which is also an exponentiation of 3, in descending order, adding the coefficient a_k multiplied by the value r¹ to said accumulator;

c) cubing said accumulator;

d) obtaining the values r^k for each number k which when multiplied by 3 a result is less than said degree and the result was not chosen in b);

e) for each number k from d), adding the value r^k obtained in d) multiplied by the coefficient a_3k to said accumulator;

f) cubing said accumulator;

g) for all remaining coefficients a_k, adding the corresponding component a_k r^k to said accumulator; and

h) outputting a final value in said accumulator representing a(r).

14. The method according to claim 13 wherein said values r^k are pre-computed and stored in a memory accessible by a computing device.

15. The method according to claim 13 wherein said values r^k are computed by a computing device during execution of said method.

16. A computer readable medium comprising computer executable instructions for evaluating a polynomial a(x) of a finite field of characteristic 3 at an element r, said polynomial a(x) having a degree and being equivalent to a sum of a plurality of components having respective coefficients a_k combined with corresponding values r^k, said computer executable instructions comprising instructions for:

a) initializing an accumulator to zero;

b) for each number k which is less than said degree and greater than 3, and which is also an exponentiation of 3, in descending order, adding the coefficient a_k multiplied by the value r¹ to said accumulator;

c) cubing said accumulator;

d) obtaining the values r^k for each number k which when multiplied by 3 a result is less than said degree and the result was not chosen in b);

e) for each number k from d), adding the value r^k obtained in d) multiplied by the coefficient a_3k to said accumulator;

f) cubing said accumulator;

g) for all remaining coefficients a_k, adding the corresponding component a_k r^k to said accumulator; and

h) outputting a final value in said accumulator representing a(r).

17. The computer readable medium according to claim 16 wherein said values r^k are pre-computed and stored in a memory accessible by a computing device.

18. The computer readable medium according to claim 16 wherein said values r^k are computed by a computing device during execution of said method.