Ring arithmetic method, system, and apparatus

1. A method of encrypting data, comprising:

choosing a modulus C for modular calculations, wherein C is a w-bit number, and wherein the modulus C is selected from the group consisting of (a) w-big and w-heavy, and (b) w-little and w-light; and

using the modulus to encrypt data through a process involving a ring arithmetic function; wherein the modulus C is calculated by a process including

(a) splitting a number P<2 2w into 2 w-bit words H 1 and L 1 ;

(b) calculating S 1 =L 1 +(H 1 2 x1 )+(H 1 2 x2 )+ . . . +(H 1 2 xk )+H 1 , wherein (w−3)/2>x 1 >x 2 > . . . >x k >0 and k<<w;

(c) splitting S 1 into two w-bit words H 2 and L 2 ;

(d) computing S 2 =L 2 +(H 2 2 x1 )+(H 2 2 x2 )+ . . . (H 2 2 x1 )+H 2 ;

(e) computing S 3 =S 2 +(2 x1 + . . . +2 xk +1);

(f) determining the modulus C by comparing S 3 to 2w, wherein the modulus C=S 2 if S 3 <2 w , and wherein the modulus C=S 3 −2 w if S 3 ≧2 w ;

wherein the modulus C is a residue.

2. The method of claim 1 , wherein the modulus C is of the form 2 w −L, and wherein L is a low Hamming weight odd integer less than 2 (w-1)/2 .

3. The method of claim 1 , wherein the modulus C is of the form 2 w +L, and wherein the modulus C has a Hamming weight close to 1.

4. The method of claim 1 , wherein the method of encrypting data comprises a method of cryptographic hashing.

5. The method of claim 1 , wherein the modulus C is w-big and w-heavy.

6. The method of claim 1 , wherein the modulus C is w-little and w-light.

7. The method of claim 1 , wherein C=2 w −2 x1 −2 x2 − . . . −2 xk −1, wherein (w−3)/2>x 1 >x 2 > . . . >x k >0, and wherein k>>w.

8. The method of claim 1 , further comprising:

choosing a first basis (m 1 , m 2 , . . . m t ) and a second basis (m t+1 , m t+2 , . . . m 2t ), wherein m 1 , . . . m 2t are moduli;

calculating a product M=m 1 m 2 . . . m t ;

calculating a product W=m t+1 m t+2 . . . m 2t ; and

calculating a product ABM −1 mod p for n-bit numbers A and B by (a) computing Q mod M in the first basis such that AB+Qp=RM for some integral value R and for a number p which is prime relative to M and W; (b) converting Q to the second basis, Q mod W; and (c) computing R in the second basis, R mod W, wherein R=(AB+Qp) M −1 mod W and R mod p=ABM −1 mod p.

9. The method of claim 8 wherein, for i=1 to 2t, 2 k−1 ≦m i ≦2 k , and wherein m 1 , . . . , m 2t are pairwise mutually prime.

10. The method of claim 9 , wherein t≧(n+1)/k, where n is the bit length of the numbers being multiplied.

11. The method of claim 1 , further comprising:

performing a ring arithmetic function on numbers, including (a) using a residue number multiplication process, (b) converting to a first basis using a mixed radix system, and (c) converting to a second basis using a mixed radix system.

12. A method of encrypting data, comprising:

choosing a modulus C for modular calculations, wherein C is a w-bit number, and wherein the modulus C is selected from the group consisting of (a) w-big and w-heavy, and (b) w-little and w-light; and

using the modulus to encrypt data through a process involving a ring arithmetic function; wherein the method further comprises

choosing a first basis (m 1 , m 2 , . . . m t ) and a second basis (m t+1 , m t+2 , . . . m 2t ), wherein m 1 , . . . , m 2t are moduli,

calculating a product M=m 1 m 2 . . . m t ,

calculating a product W=m t+1 m t+2 . . . m 2t , and

calculating a product ABM −1 mod p for n-bit numbers A and B by (a) computing Q mod M in the first basis such that AB+Qp=RM for some integral value R and for a number p which is prime relative to M and W; (b) converting Q to the second basis, Q mod W; and (c) computing R in the second basis, R mod W, wherein R=(AB+Qp) M −1 mod W and R mod p=ABM −1 mod p.

13. The method of claim 12 , further comprising:

performing a ring arithmetic function on numbers, including (a) using a residue number multiplication process, (b) converting to a first basis using a mixed radix system, and (c) converting to a second basis using a mixed radix system.

14. The method of claim 12 , wherein the modulus C is of the form 2 w −L, and wherein L is a low Hamming weight odd integer less than 2 (w−1)/2 .

15. The method of claim 12 , wherein the modulus C is of the form 2 w +L, and wherein the modulus C has a Hamming weight close to 1.

16. The method of claim 12 , wherein the method of encrypting data comprises a method of cryptographic hashing.

17. The method of claim 12 , wherein the modulus C is w-big and w-heavy.

18. The method of claim 12 , wherein the modulus C is w-little and w-light.

19. The method of claim 12 , wherein C=2 w −2 x1 −2 x2 − . . . −2 xk −1, wherein (w−3)/2>x 1 >x 2 > . . . >x k >0, and wherein k>>w.

20. The method of claim 12 wherein, for i=1 to 2t, 2 k−1 ≦m i ≦2 k , and wherein m 1 , . . . , m 2t are pairwise mutually prime.

21. The method of claim 20 , wherein t≧(n+1)/k, where n is the bit length of the numbers being multiplied.

22. The method of claim 21 , wherein p is an n-bit number, and wherein p is a prime number.

23. The method of claim 20 , further comprising converting R to the first basis, R mod M.

24. The method of claim 12 , wherein the step of calculating a product ABM −1 mod p is performed iteratively and includes at least first and second subsequent iterations, and wherein the value of R calculated in the first iteration is utilized as the input value of R in the second iteration.

25. The method of claim 12 , wherein the data is encrypted using asymmetric encryption.

26. The method of claim 12 , wherein the data is encrypted using symmetric encryption.

27. The method of claim 12 , further comprising:

performing a ring arithmetic function on numbers, including (a) using a residue number multiplication process, (b) converting to a first basis using a mixed radix system, and (c) converting to a second basis using a mixed radix system.