A Design and Implementation of Montgomery Modular Multiplier

Large integer multiplication is that the critical operation to design a modular multiplier. Karatsuba algorithm (K-Algorithm) to separate the operands into 2 elements is generally used to design a large integer multiplier. During this paper, we tend to firstly propose a design of 258-bit multiplier based on K-3 algorithm deduced by K-Algorithm, with those hardware resources will be reduced than K-Algorithm. Then we tend to construct a 128-bit four stage pipelined Montgomery modular multiplier on the base of proposed multiplier. Finally, we tend to implement the design of standard multiplier on Virtex-6 FPGA platform. Additionally, our design will obtain the results of Montgomery modular multiplier for each clock. Compared with different designs on FPGA, our design shows a better performance in term of area-time product.