Recursive Double-Size Modular Multiplications from Euclidean and Montgomery Multipliers

Masayuki YOSHINO  Katsuyuki OKEYA  Camille VUILLAUME  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E93-A   No.1   pp.180-187
Publication Date: 2010/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E93.A.180
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Mathematics
modular multiplication,  RSA,  efficient implementation,  low-end device,  double-size technique,  

Full Text: PDF>>
Buy this Article

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 2-bit modular multiplication to work on most -bit modular multipliers. However, the cost of the quotient computation rises sharply when computing modular multiplications larger than 2 bits with a recursive approach. This paper addresses the computation cost and improves on previous 2-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 2-bit Montgomery multiplication algorithm to return both of the remainder and the quotient.