Presentation | 2008-11-17 Hardware Algorithm for Division in GF(2^m) Based on the Extended Euclid's Algorithm Accelerated with Parallelization of Modular Reductions Katsuki KOBAYASHI, Naofumi TAKAGI, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | We propose a fast hardware algorithm for division in GF(2^m). It is based on the extended Euclid's algorithm and requires only one iteration to perform the operations that require two iterations of previously reported division algorithms based on the extended Euclid's algorithm. Since the algorithm performs modular reductions in parallel by changing the order of execution of the operations, a circuit based on this algorithm has almost the same critical path delay as the previously proposed ones. The circuit computes division in m clock cycles, whereas the previously proposed circuits take 2m-1 or more clock cycles. By logic synthesis, the computation time of the circuit is estimated to over 35% shorter than that of a previously proposed circuit. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Galois field / Division / Euclid's algorithm |
Paper # | VLD2008-65,DC2008-33 |
Date of Issue |
Conference Information | |
Committee | DC |
---|---|
Conference Date | 2008/11/10(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 | Dependable Computing (DC) |
---|---|
Language | ENG |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Hardware Algorithm for Division in GF(2^m) Based on the Extended Euclid's Algorithm Accelerated with Parallelization of Modular Reductions |
Sub Title (in English) | |
Keyword(1) | Galois field |
Keyword(2) | Division |
Keyword(3) | Euclid's algorithm |
1st Author's Name | Katsuki KOBAYASHI |
1st Author's Affiliation | Dept. of Information Engineering, Graduate School of Information Science, Nagoya Univ.() |
2nd Author's Name | Naofumi TAKAGI |
2nd Author's Affiliation | Dept. of Information Engineering, Graduate School of Information Science, Nagoya Univ. |
Date | 2008-11-17 |
Paper # | VLD2008-65,DC2008-33 |
Volume (vol) | vol.108 |
Number (no) | 299 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |