Speed enhanced cryptographic method and apparatus

1. A method for performing a cryptographic operation that comprises transforming digital information, the method comprising:

providing digital information;

providing a digital operator having a component selected from a large set of elements;

expanding the component into a plurality of factors, each factor having a low hamming weight; and

transforming the digital information using the digital operator, said transforming comprising computing multiples;

said method further comprising:

selecting a ring R;

selecting an R-module M;

selecting two or more subsets R 1 , R 2 , . . . , R k of R with the property that r 1 is an element in R 1 , r 2 is an element in R 2 , . . . and r k is an element in R k ;

computing r*m, where r is in R and m is in M, by expanding r as r 1 *r 2 . . . r k , where k is an integer and computing the quantity r 1 *(r 2 *( . . . (r k *m).

2. The method of claim 1 , wherein the cryptographic operation is selected from a group consisting of key generation, encryption, decryption, creation of a digital signature, verification of a digital signature, creation of a digital certificate, authentication of a digital certificate, identification, pseudorandom number generation and computation of a hash function.

3. The method of claim 1 , wherein each r k has a Hamming weight that is less than about 15.

4. The method of claim 1 , wherein each r k has a Hamming weight that is less than about 10.

5. The method of claim 1 , wherein the subset R i is a subset of R consisting of elements of the form,

a 1 t e(1) +a 2 t e(2) + . . . +a n t e(n) ,

where n is an integer.

6. The method of claim 5 , wherein each of the elements a 1 , . . . , a n are chosen from the set {0,1}.

7. The method of claim 5 , wherein each of the elements a 1 , . . . , a n are chosen from the set {−1,0,1}.

8. The method of claim 1 , wherein the subset R i is a subset of R consisting of polynomials in elements of t 1 , . . . , t k of R having coefficients a 1 , . . . , a k taken from a subset A of R where k is an integer.

9. The method of claim 8 , wherein each of the coefficients a 1 , . . . , a k is chosen from the set {0,1}.

10. The method of claim 8 , wherein each of the coefficients a 1 , . . . , a k is chosen from the set {−1,0,1}.

11. The method of claim 1 , wherein the ring R is the ring of integers, the R-module M is a group of nonzero elements in the field GF(p m ) with p m elements, and wherein the subsets R 1 , . . . , R k consist of integers of the form

a 1 p e(1) +a 2 p e(2) + . . . +a n p e(n) ,

wherein n is an integer that is less than m and wherein a 1 , . . . , a n are elements of the set {0,1}.

12. The method of claim 1 , wherein the ring R is the ring of integers, the R-module M is a group of nonzero elements in the field GF(p m ) with p m elements, and wherein the subsets R 1 , . . . , R k consist of integers of the form

a 1 p e(1) +a 2 p e(2) + . . . +a n p e(n) ,

wherein n is an integer that is less than m and wherein a 1 , . . . , a n are elements of a small set of integers A.

13. The method of claim 1 , wherein the ring R is an endomorphism ring of a group of points E(GF(q)) of an elliptic curve E over a finite field GF(q).

14. The method of claim 1 , wherein the module M is a group of points e(GF(q)) of an elliptic curve E over a finite field GF(q).

15. The method of claim 5 , wherein the ring R is an endomorphism ring of a group of points E(GF(q)) of an elliptic curve E over a finite field GF(q) of characteristic p, wherein the module M is a group of points E(GF(q)) and wherein the element t is a p-power Frobenius map.

16. The method of claim 5 , wherein the ring R is an endomorphism ring of a group of points E(GF(q)) of an elliptic curve E over a finite field GF(q) of characteristic p, wherein the module M is a group of points E(GF(q)) and wherein the element t is a point halving map.

17. The method of claim 1 , wherein the ring R is a ring of polynomials modulo an ideal A[X]/I, wherein A is a ring and I is an ideal of A[X], and wherein the subsets R 1 , . . . , R k are sets of polynomials with few nonzero terms.

18. The method of claim 17 , wherein the ideal I is the ideal generated by the polynomimial X N −1.

19. The method of claim 17 , wherein the ring R is a finite ring Z/qZ of integers modulo q, wherein q is a positive integer.

20. The method of claim 5 , wherein the ring R is a ring of polynomials modulo an ideal A[X]/I, wherein A is a ring and I is an ideal of A[X], and wherein the element t is the polynomial X in R.

21. The method of claim 20 , wherein the deal I is the ideal generated by the polynomimial X N −1.

22. The method of claim 20 , wherein the ring R is a finite ring Z/qZ of integers modulo q, wherein q is a positive integer.

23. A computer readable medium containing instructions for a method for performing a cryptographic operation that comprises transforming digital information, the method comprising:

providing digital information;

providing a digital operator having a component selected from a large set of elements;

expanding the component into a plurality of factors, each factor having a low hamming weight; and

transforming the digital information using the digital operator, said transforming comprising computing multiples;

said method further comprising:

selecting a ring R;

selecting an R-module M;

selecting two or more subsets R 1 , R 2 , . . . , R k of R with the property that r 1 is an element in R 1 , r 2 is an element in R 2 , . . . and r k is an element in R k ;

computing r*m, where r is in R and m is in M, by expanding r as r 1 * r 2 * . . . r k , where k is an integer and computing the quantity r 1 *(r 2 *( . . . (r k *m).

24. The computer readable medium of claim 23 , containing instructions for a method wherein the subset R i is a subset of R consisting of elements of the form,

a 1 t e(1) +a 2 t e(2) + . . . +a n t e(n) ,

where n is an integer.

25. The computer readable medium of claim 23 , containing instructions for a method wherein the subset R i is a subset of R consisting of polynomials in elements of t 1 , . . . , t k of R having coefficients a 1 , . . . , a k taken from a subset A of R where k is an integer.

26. The computer readable medium of claim 23 , containing instructions for a method wherein the ring R is the ring of integers, the R-module M is a group of nonzero elements in the field GF(p m ) with p m elements, and wherein the subsets R 1 , . . . , R k consist of integers of the form

a 1 p e(1) +a 2 p e(2) + . . . +a n p e(n) ,

wherein n is an integer that is less than m and wherein a 1 , . . . , a n are elements of the set {0,1}.

27. The computer readable medium of claim 23 , containing instructions for a method wherein the ring R is the ring of integers, the R-module M is a group of nonzero elements in the field GF(p m ) with p m elements, and wherein the subsets R 1 , . . . , R k consist of integers of the form

a 1 p e(1) +a 2 p e(2) + . . . +a n p e(n) ,

wherein n is an integer that is less than m and wherein a 1 , . . . , a n are elements of a small set of integers A.

28. The computer readable medium of claim 23 , containing instructions for a method wherein the ring R is an endomorphism ring of a group of points E(GF(q)) of an elliptic curve E over a finite field GF(q).

29. The computer readable medium of claim 23 , containing instructions for a method wherein the module M is a group of points e(GF(q)) of an elliptic curve E over a finite field GF(q).

30. The computer readable medium of claim 24 , containing instructions for a method wherein the ring R is an endomorphism ring of a group of points E(GF(q)) of an elliptic curve E over a finite field GF(q) of characteristic p, wherein the module M is a group of points E(GF(q)) and wherein the element t is a p-power Frobenius map.

31. The computer readable medium of claim 24 , containing instructions for a method wherein the ring R is an endomorphism ring of a group of points E(GF(q)) of an elliptic curve E over a finite field GF(q) of characteristic p, wherein the module M is a group of points E(GF(q)) and wherein the element t is a point halving map.

32. The computer readable medium of claim 23 , containing instructions for a method wherein the ring R is a ring of polynomials modulo an ideal A[X]/I, wherein A is a ring and I is an ideal of A[X], and wherein the subsets R 1 , . . . , R k are sets of polynomials with few nonzero terms.

33. The computer readable medium of claim 24 , containing instructions for a method wherein the ring R is a ring of polynomials modulo an ideal A[X]/I, wherein A is a ring and I is an ideal of A[X], and wherein the element t is the polynomial X in R.