Patent ID: 7590235

Claim:
A method of performing a reduction operation in a cryptographic calculation in a digital computer, the method comprising: selecting a modulus having a first section with a plurality of “1” Most Significant Word states and a second section which further comprises: a plurality of “1” or “0” states whereby a number formed of the two sections is a modulus; and operating a reduction operation on the modulus comprising: multiplying a first variable n 0 ′ by a second variable r 3 to produce a first result; adding the first result to a third variable r 1 and B multiplied by a fourth variable r 2 to produce a first sum, wherein the first sum corresponds to a first equation: n 0 ′r 3 +Br 2 +r 1 ; dividing the first sum into an upper half and a lower half; multiplying the upper half by the first variable n 0 ′ to produce a second result; adding the second result to the lower half and a fifth variable r 0 to produce a second sum, thereby permitting use of the second sum as the modulus; and using the modulus in the cryptographic calculation.