Patent ID: 7607165

Claim:
Automatic computing machinery having logic embodied thereon for performing a method of modular reduction processing of a number which is represented by a sequence of digits, comprising: providing a modular reduction processor; receiving a number x, wherein number x is provided in radix b form and is represented by sequence of 2k digits such that {x i |i=0, 1, 2, . . . , 2k−1}; and processing x, via the modular reduction processor, wherein x is processed least significant digit first and in digits in increasing order of significance thereafter, wherein processing x comprises: dividing x by b k+1 to produce q 1 ; multiplying q 1 by μ to produce q 2 , wherein μ is given in radix b form and is represented by sequence of k+1 digits such that μ=└b 2k /m┘, wherein m is modulus given in radix b form and is represented by sequence of k digits such that {m i |i=0, 1, 2, . . . , 2k−1} wherein m k−1 ≠0); dividing q 2 by b k+1 to produce q 3 ; multiplying q 3 by m; reducing the product of q 3 multiplied by m modulo b k+1 to produce r 2 ; reducing x modulo b k+1 to produce r 1 ; subtracting r 2 from r 1 to produce r; and determining which of the following is true: r is non-negative and r a1 is negative, wherein r a1 is r−m; r is non-negative and r a1 is non-negative and r a2 is negative, wherein r a2 is r−2m; r is non-negative and r a2 is non-negative; r is negative and r pa1 is negative, wherein r pa1 =r+b k+1 −m; r is negative and r pa1 is non-negative and r pa2 is negative, wherein r pa2 =r+b k+1 −2m; and r is negative and r pa2 is non-negative, wherein if r is non-negative and r a1 is negative, x mod m=r, wherein if r is non-negative and r a1 is non-negative and r a2 is negative, x mod m=r−m, wherein if r is non-negative and r a2 is non-negative, x mod m=r−2m, wherein if r is negative and r pa1 is negative, x mod m=r+b k+1 , wherein if r is negative and r pa1 is non-negative and r pa2 is negative, x mod m=r+b k+1 −m, and wherein if r is negative and r pa2 is non-negative, x mod m=r+b k+1 −2m.