Hardware design for multiplicative modular inverse based on table look up technique
Satyanarayana Vollala, B. Shameedha Begum, N. Ramasubramanian · 2015
Multiplicative modular inverse is a vital operation carried out in most of the public-key systems that can accelerate the entire modular exponentiation process. In this paper a new algorithm has been proposed to evaluate modular inverse that can accept any type of integer modulus input without imposing any restriction. The calculated values are stored in a look-up table and hence named LUK-mod-inverse algorithm. The proposed algorithm uses look-up table structure that has been designed in hardware that explores memoization technique. All the stored modular inverse values can be retrieved in just two clock cycles. The simulation and synthesis has been carried out by using Xilinx-14.6 ISE for usage in FPGA board and the results have shown a positive trend in terms of frequency, clock cycles and throughput. The proposed hardware design is able to compute the multiplicative modular inverse with in 2 clock cycles only, it is able to improve the frequency by 32.22% and throughput by 600% for 64-bits integers.