Recursive Double-Size Modular Multiplications without Extra Cost for Their Quotients

摘要

A technique for computing the quotient ([ab/n]) of Euclidean divisions from the difference of two remainders (ab (mod n) - ab (mod n + 1)) was proposed by Fischer and Seifert. The technique allows a 2l-bit modular multiplication to work on most l-bit modular multipliers. However, the cost of the quotient computation rises sharply when computing modular multiplications larger than 2l bits with a recursive approach. This paper addresses the computation cost and improves on previous 2l-bit modular multiplication algorithms to return not only the remainder but also the quotient, resulting in an higher performance in the recursive approach, which becomes twice faster in the quadrupling case and four times faster in the octupling case. In addition to Euclidean multiplication, this paper proposes a new 2l-bit Montgomery multiplication algorithm to return both of the remainder and the quotient.