Computer-implemented method and computer for performing modular reduction
US5724279A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Aug 25, 1995 |
| Grant date | Mar 3, 1998 |
| Priority date | — |
| Expiry date | Aug 25, 2015 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F7/72
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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 result…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.