DocumentCode
975547
Title
Analyzing and comparing Montgomery multiplication algorithms
Author
Koç, Çetin Kaya ; Acar, Tolga ; Kaliski, Burton S., Jr.
Author_Institution
Oregon State Univ., Corvallis, OR, USA
Volume
16
Issue
3
fYear
1996
fDate
6/1/1996 12:00:00 AM
Firstpage
26
Lastpage
33
Abstract
Montgomery multiplication methods constitute the core of modular exponentiation, the most popular operation for encrypting and signing digital data in public-key cryptography. In this article, we study the operations involved in computing the Montgomery product, describe several high-speed, space-efficient algorithms for computing MonPro(a, b), and analyze their time and space requirements. Our focus is to collect several alternatives for Montgomery multiplication, three of which are new. However, we do not compare the Montgomery techniques to other modular multiplication approaches
Keywords
computational complexity; digital arithmetic; public key cryptography; Montgomery multiplication; Montgomery product; digital data; modular exponentiation; public-key cryptography; space requirements; time requirements; Algorithm design and analysis; Computer aided instruction; Difference equations; Microprocessors; Performance analysis; Read-write memory; Registers; Timing;
fLanguage
English
Journal_Title
Micro, IEEE
Publisher
ieee
ISSN
0272-1732
Type
jour
DOI
10.1109/40.502403
Filename
502403
Link To Document