A dual-field modular division algorithm and architecture for application specific hardware

This paper presents a dual-field modular division (inversion) algorithm and its hardware design. The algorithm is based on the Extended Euclidean and the Binary GCD algorithms. The use of counters to keep track of the difference between field elements in this algorithm eliminates the need for comparisons which are usually expensive and time-consuming. The algorithm has simple control flow and arithmetic operations making it suitable for application specific hardware implementation. The proposed architecture uses a scheduling method to reduce the number of hardware resources without significantly increasing the total execution time. Its datapath efficiently supports all the operations in the algorithm and uses carry-save unified adders for reduced critical path delay, making the proposed architecture faster than other previously proposed designs. Experimental results using synthesis for AMI 0.5 /spl mu/m CMOS technology are shown and compared with other dividers.