Patent ID: 7853014

Claim:
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.