Efficient finite field multiplication in normal basis
US6389442B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 28, 1998 |
| Grant date | May 14, 2002 |
| Priority date | — |
| Expiry date | Dec 28, 2018 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F7/724
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The invention provides improved techniques for multiplication of signals represented in a normal basis of a finite field. An illustrative embodiment includes a first rotator which receives a first input signal representative of a first normal basis field element (a0 a1 . . . am−1), and a second rotator which receives a second input signal representative of a second normal basis field element (b0 b1 . . . bm−1). A word multiplier receives output signals from the first and second rotators, corresponding to rotated representations of the first and second elements, respectively, and processes the rotated representations w bits at a time to generate an output signal representative of a product of the first and second elements, where w is a word length associated with the word multiplier. The rotated representation of the first element may be given by A[i]=(ai ai+1 . . . ai+w−1), the rotated representation of the second element may be given by B[i]=(bi bi+1 . . . bi+w−1), and the product may be given by c=(C[0], C[w], C[2w], . . . , C[m−w]), where C[i]=(ci Ci+1 . . . ci +w−1), m is the degree of the finite field, w is the word length, and i=0, 1, . . .…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.