An algorithm and hardware architecture for integrated modular division and multiplication in GF(p) and GF(2n)

This work presents an algorithm and architecture that integrates modular division and multiplication in both GF(p) and GF(2ⁿ) fields (unified). The algorithm is based on the extended binary GCD algorithm for modular division and on the Montgomery´s method for modular multiplication. For the division operation, the proposed algorithm uses a counter to keep track of the difference between two field elements and this way eliminate the need for comparisons which are usually expensive and time-consuming. The proposed architecture 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 μm CMOS technology are shown and compared with other dividers and multipliers.