Method for efficient modular polynomial division in finite fields f(2{circumflex over ( )}m)
US6721771B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Aug 28, 2000 |
| Grant date | Apr 13, 2004 |
| Priority date | — |
| Expiry date | Dec 19, 2021 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F7/721
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The present invention provides a method for performing an inversion and multiply in a single operation as a polynomial divide operation. As a result, the invention reduces the number of mathematical operations needed to perform point doubling and point addition operations. An elliptic curve cryptosystem using the present invention can be made to operate more efficiently using the present invention. An elliptic curve crypto-accelerator can be implemented using the present invention to dramatically enhance the performance of the elliptic curve cryptosystem. The invention uses five registers A, B, U, V, and M, to accomplish a polynomial divide operation. Four registers A, B, U, and V are initialized with values so that the registers maintain a number of invariant relationships. The registers store initial values a(t)=x(t), u(t)=y(t), b(t)=prime(t), and v(t)=0. Here the polynomials in registers A, U, B, and V are denoted as a(t), u(t), b(t), and v(t), respectively. Register M stores the irreducible polynomial prime(t). By applying a series of invariant operations to the registers, the register values are systematically reduced until registers A and B have a value of one. At that point,…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.