| Presentation | 2001/6/22 An Algorithm for Division on Finite Fields Based on Stein's Algorithm Yasuaki Watanabe, Naofumi Takagi, Kazuyoshi Takagi, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A VLSI algorithm for division on finite fields with the polynomial basis representation is proposed. Stein's algorithm for integer GCD computation is modified to polynomial GCD computation and extended to division on finite fields. Division on GF(2^m) is carried out through iteration of simple operations, such as shifts and additions on GF(2^m). A divider on GF(2^m) based on the algorithm has a linear array structure with a bit-slice feature and carries out division in at most 2m clock cycles. The number of gates in the circuit is proportional to m and the depth of the circuit is independent of m. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | multiplicative inversion on finite fields / division on finite fields / hardware algorithm / VLSI algorithm / public-key cryptosystem |
| Paper # | CAS2001-42,VLD2001-59,DSP2001-61 |
| Date of Issue |
| Conference Information | |
| Committee | DSP |
|---|---|
| Conference Date | 2001/6/22(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Digital Signal Processing (DSP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | An Algorithm for Division on Finite Fields Based on Stein's Algorithm |
| Sub Title (in English) | |
| Keyword(1) | multiplicative inversion on finite fields |
| Keyword(2) | division on finite fields |
| Keyword(3) | hardware algorithm |
| Keyword(4) | VLSI algorithm |
| Keyword(5) | public-key cryptosystem |
| 1st Author's Name | Yasuaki Watanabe |
| 1st Author's Affiliation | Graduate School of Engineering, Nagoya University() |
| 2nd Author's Name | Naofumi Takagi |
| 2nd Author's Affiliation | Graduate School of Engineering, Nagoya University |
| 3rd Author's Name | Kazuyoshi Takagi |
| 3rd Author's Affiliation | Graduate School of Engineering, Nagoya University |
| Date | 2001/6/22 |
| Paper # | CAS2001-42,VLD2001-59,DSP2001-61 |
| Volume (vol) | vol.101 |
| Number (no) | 146 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |