Patent ID: 7809133

Claim:
A cryptographically secure, computer hardware-implemented modular reduction method, comprising: precomputing and storing in memory a constant U representing a bit-scaled reciprocal of a modulus M; computing an estimated quotient value q for a number X to be reduced modulo M, wherein said computing is executed upon X in a computation unit by a multiplication by said constant U and by bit shifts of X and a shift of said multiplication; generating in a random number generator a random error value E; applying said generated random error value E to said estimated quotient value q to obtain a randomized quotient q′=q−E, wherein the random number generator has a specified error limit of one-half word, whereby 0≦E<(2 w/2 −1), with “w” being the word size of the computation unit in bits; and calculating a remainder R′=X−q′M in said computation unit, said remainder R′ being larger than said modulus M but congruent to X modulo M.