Method for the implementation of modular reduction according to the Montgomery method
US5764554A · kind A · utility
Inventor
Key dates
| Filing date | Nov 7, 1995 |
| Grant date | Jun 9, 1998 |
| Priority date | — |
| Expiry date | Nov 7, 2015 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F7/728
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method for implementing modular reduction according to the Montgomery method, wherein a binary data element C is encoded on a number c of bits, grouped together in m' words of k bits, with m' and k as integers, m' being such that m'*k>c>(m'-1)*k, a non-zero binary data element N is encoded on a number n of bits. According to the disclosed method, to produce C mod N, steps are carried out for the production of a binary data element J0, associated with N, the production of at least one binary data element H having the form 2.sup.f(C,N), with f(C,N) as an integer representing the size of C and the parity of N, and the providing firstly of C, at the parallel input of a multiplication circuit having one serial input, one parallel input and one serial output, and secondly of H at the serial input of this same multiplication circuit.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.