High speed montgomery value calculation
US6240436A · kind A · utility
24Cited by
2References
14Claims
0Family size
Assignee
Inventor
Key dates
| Filing date | Mar 30, 1998 |
| Grant date | May 29, 2001 |
| Priority date | — |
| Expiry date | Mar 30, 2018 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F7/728
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and apparatus for performing high-speed computation of a Montgomery value defined as 2.sup.2k mod(n) for an arbitrary modulus n is disclosed. After loading the value of 2.sup.(h*m)+1 into a first register and the value of the modulus n in a second register, the bits of modulus n are shifted in a most significant bit direction before a repeated modular reduction and squaring process. This allows the computation of the Montgomery value for modulus values of arbitrary sizes while reducing the number of computations required by a processor with a limited operand size.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.