Patent ID: 7805480

Claim:
A cryptographically secure, computer hardware-implemented modular polynomial reduction method in the binary finite field GF(2 n ), comprising: precomputing and storing in memory a polynomial constant u(x) representing a bit-scaled reciprocal of a polynomial modulus m(x); estimating an approximate polynomial quotient q for a polynomial p(x) to be reduced modulo m(x), wherein said estimating is executed upon p(x) in a computation unit by a polynomial multiplication over GF (2 n ) said constant u(x) and by bits shifts; generating in a random number generator a random polynomial error value E(x) and applying said polynomial error value to said approximate polynomial quotient to obtain a randomized polynomial quotient q′(x)=q(x)+E(x); and calculating a polynomial remainder r′(x)=p(x)+q′(x)·m(x) in said computation unit, said remainder r′(x) being of high degree than said modulus m(x) but congruent to p(x) modulo m(x) and where the degree of p(x) is less than or equal to 2k+1.