Hardware Algorithm for Division in GF(2~m) Based on the Extended Euclid's Algorithm Accelerated with Parallelization of Modular Reductions

摘要

We propose a fast hardware algorithm for division in GF(2m). 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 pro­posed 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.