Abstract

This invention provides a computer-implemented method for performing a modular reduction operation "X mod M" and doing modular arithmetic on a computer. In a first stage of the method, the number X=<xk xk-1 . . . x1 x0 >, written in base ଱, is reduced from k+1 blocks to an n+1 block integer Y that is equivalent to X modulo M. The stage one process is achieved via a reduce-and-compensate scheme that involves a series of simple multiply and add/subtract operations that are much faster than conventional techniques for performing the division remainder operation "X mod M." The reduction phase requires reducing the number X to an intermediate value that is equal to X mod ଱k. The compensate phase requires adjustment by an amount sufficient to produce an incrementally reduced value XR which is equivalent to X modulo M. This compensate phase can be implemented by adding back a multiple of ଱n+1 mod M, or by subtracting a multiple of M-(଱n+1 mod M). The stage two process further reduces the n+1 block integer Y to an equivalent n block integer Z. Although intermediate computations may stop after stage one or stage two, the resulting integer Z might be larger than the modulus M, and thus still require further reduction to produce a final result. Accordingly, the third stage involves reducing the integer Z to an equivalent remainder R such that 0ࣘR<M.