For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2010/01/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
modular multiplication, RSA, efficient implementation, low-end device, double-size technique,
Full Text: PDF>>
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.