Modular multiplication method and the system for processing data
US5073870A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | Jan 29, 1990 |
| Grant date | Dec 17, 1991 |
| Priority date | — |
| Expiry date | Jan 29, 2010 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F7/722
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
To markedly improve the computational speed of A.times.B modulo N computation as compared with the prior-art Baker's method where A denotes a multiplicand: B denotes a multiplier; and N denotes a modulus, the number of multiply-addition and division (modular) substractions is reduced on the basis of any given same higher radix number r. In practice, the modular subtractors c(k)N are previously determined on the basis of the partial products b(k-1)A at the succeeding processing stage (k-1) to reduce the absolute value of the partial remainder R(k) down on a value less than a modulus N, so that bit overflow from a predetermined computational range can be prevented. For instance, when the partial product b(k)A at the succeeding processing stage (k-1) is large, the modular subtracter c(k)N at the current stage (k) is also determined large. Further, the most significant bit of the multiplicand A is eliminated by transforming the multiplicand A from a range within [0, N-1] to a range [-N/2, N/2] to reduce the absolute value of the partial product. This is necessary to apply the same radix number r to both the partial products and the modular subtracters.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.