Computer-implemented method and computer for performing modular reduction

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=<x.sub.k x.sub.k-1 . . . x.sub.1 x.sub.0 >, written in base .alpha., 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 .alpha..sup.k. The compensate phase requires adjustment by an amount sufficient to produce an incrementally reduced value X.sub.R which is equivalent to X modulo M. This compensate phase can be implemented by adding back a multiple of .alpha..sup.n+1 mod M, or by subtracting a multiple of M-(.alpha..sup.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.ltoreq.R<M.