Improvement of Interleaved Multiplication Algorithm

An improved modular multiplication algorithm based on the interleaved multiplication is presented in this paper. Carry save addition (CSA), redundant representation, a fast lookup table and a counter register are used to improve this algorithm. Carry save addition and redundant representation are used to replace other additions like carry select addition, carry lookahead addition and so on, because carry propagation brought by those additions can be prevented by carry save addition, and redundant representation can make the arithmetic operations fast without carry propagation. The fast lookup table with only 7 pre-calculated values can minimize the number of additions, and can only be addressed once in one iteration, which not only speed up, but also save area compared with other literatures used lookup tables. The iteration number can be reduced by a counter register being added in this improved method to compute the number of 0 from the most significant bit of one operand like X. Analysis and emulation result shows the area and time complexity (AT) of the improved method is equal or even less than 2n².