Design and Implementation of a Hardware Divider in Finite Field

[attachment=17937]
INTRODUCTION
Division in finite fields is an important arithmetic
operation that is widely used in channel coding,
cryptography, error correction and code construction
applications. An algorithm that is suitable for hardware
implementation should require few clock cycles and
simple arithmetic operations. One such algorithm has been
proposed for modular division and its inverse in GF(p) is
called the Unified Modular Division (UMD) algorithm [1].
This algorithmic approach can be used to determine
modular inverse in both integer and Montgomery domains.
This method is based on extended Euclidean algorithm [2]
and binary GCD algorithm [3].



SIMULATION AND SYNTHESIS
Initial fixed-point verification of the UMD algorithm was
developed in C-language. Hardware simulation was then
developed in Verilog HDL and tested in Aldec™
environment. Finally, complete synthesis and
implementation flow was done using Xilinx-XST™ tools.
The number of clock cycles required for binary division is
very few and its complexity in terms of number of
iterations is much less than other modular inversion
techniques as already mentioned in section 1. Some
performance results are described later in section 3.



RESULTS AND DISCUSSIONS
As already mentioned in Section 1, the complexity of this
UMD hardware approach is much less than those of
previous systolic architectures. Systolic architectures exist
as parallel-in parallel-out, serial-in parallel-out, parallel-in
serial-out and serial-in serial-out manner. The computation
time of these architectures becomes impractical when the
number of bits becomes large.
For testing our unified modular division algorithm, at least
100 random samples were used to verify the operations of
this algorithm approach with Unified Montgomery inverse
algorithm suggested in [5] and to obtain statistics.



SUMMARY AND CONCLUSION
The unified modular hardware division implementation
approach presented in this paper can be used efficiently to
compute the inverse in primary field, GF(p) for both
Montgomery and integer domains. The approach presented
here reduces the complexity of all iteration making it
faster than those of other algorithms that use comparison
operations. The simplicity of the control (15 registers, 3
multiplexers, 6 adders) and the operations used in the
design has made it suitable for decoding, code
construction and cryptographic hardware.