Fast division algorithm and its architecture over GF(2m)

In this paper, a hardware algorithm is first proposed for executing fast division over GF(2m), and then new hardware architecture is presented based on the algorithm. The algorithm is based on the existing Extended binary GCD algorithm using standard basis representation. However, the proposed method adopts a technique which uses only two 1-bit flags for comparing the magnitude of S and R while the existing methods use m-bit comparator. From implementation results, the proposed algorithm is shown to achieve the best performance in both area and speed aspects over the existing algorithms. The designed 163-bit iterative divider operates at a clock frequency of about 359 MHz on Xilinx FPGA with Virtex4-xc4vlx15 target device.