Circuit and method for fast modular multiplication
US6356636B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jul 22, 1998 |
| Grant date | Mar 12, 2002 |
| Priority date | — |
| Expiry date | Jul 22, 2018 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F7/728
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A co-processor (44) executes a mathematical algorithm that computes modular exponentiation equations for encrypting or decrypting data. A pipelined multiplier (56) receives sixteen bit data values stored in an A/B RAM (72) and generates a partial product. The generated partial product is summed in an adder (58) with a previous partial product stored in a product RAM (64). A modulo reducer (60) causes a binary data value N to be aligned and added to the summed value when a particular data bit location of the summed value has a logic one value. An N RAM (70) stores the data value N that is added in a modulo reducer (60) to the summed value. The co-processor (44) computes the Foster-Montgomery Reduction Algorithm and reduces the value of (A*B mod N) without having to first compute the value of &mgr; as is required in the Montgomery Reduction Algorithm.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.