Generic implementations of elliptic curve cryptography using partial reduction
US7240084B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 11, 2003 |
| Grant date | Jul 3, 2007 |
| Priority date | — |
| Expiry date | Apr 8, 2025 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F7/725
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A reduction operation is utilized in an arithmetic operation on two binary polynomials X(t) and Y(t) over GF(2), where an irreducible polynomial Mm(t)=tm+am−1tm−1+am−2tm−2+ . . . +a1t+a0, where the coefficients ai are equal to either 1 or 0, and m is a field degree. The reduction operation includes partially reducing a result of the arithmetic operation on the two binary polynomials to produce a congruent polynomial of degree less than a chosen integer n, with m≦n. The partial reduction includes using a polynomial M′=(Mm(t)−tm)*tn−m, or a polynomial M″=Mm(t)*tn−m as part of reducing the result to the degree less than n and greater than or equal to m. The integer n can be the data path width of an arithmetic unit performing the arithmetic operation, a multiple of a digit size of a multiplier performing the arithmetic operation, a word size of a storage location, such as a register, or a maximum operand size of a functional unit in which the arithmetic operation is performed.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.