A computer hardware-implemented cryptographic method comprising a modular polynomial reduction operation in a binary finite field, the modular polynomial reduction operation comprising: precomputing and storing in memory a polynomial constant u (x) representing a bit-scaled reciprocal of a multi-word polynomial modulus m(x) having a length defined by a number of words; estimating an approximate polynomial quotient q(x) 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 the binary finite field by said constant u(x); characterized by: said estimating further comprising performing word-size shifts; said modular polynomial reduction operation further comprising: generating in a random number generator a random polynomial error value E(x) having a degree that falls within a predetermined range 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 higher 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+w, w being a word size in bits of the computer hardware and k being the length in bit number of the words representing the modulus m(x). precomputing and storing in memory a polynomial constant u (x) representing a bit-scaled reciprocal of a multi-word polynomial modulus m(x) having a length defined by a number of words; estimating an approximate polynomial quotient q(x) 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 the binary finite field by said constant u(x); characterized by: said estimating further comprising performing word-size shifts; said modular polynomial reduction operation further comprising: generating in a random number generator a random polynomial error value E(x) having a degree that falls within a predetermined range 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 higher 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+w, w being a word size in bits of the computer hardware and k being the length in bit number of the words representing the modulus m(x). said estimating further comprising performing word-size shifts; said modular polynomial reduction operation further comprising: generating in a random number generator a random polynomial error value E(x) having a degree that falls within a predetermined range 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 higher 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+w, w being a word size in bits of the computer hardware and k being the length in bit number of the words representing the modulus m(x). generating in a random number generator a random polynomial error value E(x) having a degree that falls within a predetermined range 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 higher 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+w, w being a word size in bits of the computer hardware and k being the length in bit number of the words representing the modulus m(x).