Name
Title | ||
|---|---|---|
Rns Montgomery Multiplication Algorithm For Duplicate Processing Of Base Transformations |
Abstract | ||
|---|---|---|
This paper proposes a new algorithm to achieve about two-times speedup of modular exponentiation which is implemented by Montgomery multiplication based on Residue Number Systems (RNS). In RNS Montgomery multiplication, its performance is determined by two base transformations dominantly. For the purpose of realizing parallel processing of these base transformations, i.e. "duplicate processing," we present two procedures of RNS Montgomery multiplication, in which RNS bases a and b are interchanged, and perform them alternately in modular exponentiation iteration. In an investigation of implementation, 1.87-times speedup has been obtained for 1024-bit modular multiplication. The proposed RNS Montgomery multiplication algorithm has an advantage in achieving the performance corresponding to that the upper limit of the number of parallel processing units is doubled. |
Year | Venue | Keywords |
|---|---|---|
2003 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | RSA cryptography, modular exponentiation, residue number systems, Montgomery multiplication, base transformation |
DocType | Volume | Issue |
Journal | E86A | 1 |
ISSN | Citations | PageRank |
0916-8508 | 3 | 0.41 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| hanae nozaki | 1 | 3 | 0.41 |
| Atsushi Shimbo | 2 | 3 | 0.41 |
| Shinichi Kawamura | 3 | 255 | 22.99 |