Patent ID: 8117251

Claim:
A computing method performed by an electronic circuit for computing a modular reduction operation of at least one operand by a modulus, the method comprising: in a subtraction circuit, generating a first intermediate result representing a first intermediate result initialized with a value representing two to the power of k reduced by the modulus, where k designates the number of bits representing the modulus; generating a second intermediate result with the k lowest significant bits of said operand, at least comprising iteratively for each bit of said operand; in an addition circuit, if the state of the current bit of said operand is one, updating the second intermediate result by adding in the first intermediate result; in a shifting circuit, doubling the value of a first intermediate result by shifting the bits of the first intermediate result towards the most significant bit, where the most significant bit is the k+1th bit; in the subtraction circuit, while the most significant bit of the first intermediate result is one, updating the first intermediate result by subtracting the modulus; in the subtraction circuit, and while the most significant bit of the second intermediate result is one, updating the second intermediate result by subtracting the modulus; and in the subtraction circuit, generating an output of the modular reduction operation by updating the second intermediate result by subtracting the modulus if the second intermediate result is greater than the modulus.