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