Computer-implemented method and computer for performing modular

Details Computer-implemented method and computer for performing modular Computer-implemented method and computer for performing modular

1995-08-25

1998-03-03

Ngo, Chuong Dinh

Boots, shoes, and leggings

G06F 738

Patent

active

057242798

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.

REFERENCES:
patent: 4538237 (1985-08-01), Circello
patent: 4949293 (1990-08-01), Kawamura et al.
patent: 5499299 (1996-03-01), Takenaka et al.
patent: 5572454 (1996-11-01), Lee et al.

Affiliated with

Also associated with

Rating

Computer-implemented method and computer for performing modular does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Computer-implemented method and computer for performing modular , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer-implemented method and computer for performing modular will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2255139