|
Published Articles >> Table of Contents >> Abstract
September 2006 (Vol. 55, No. 9)
pp. 1207-1210
Improvement to Montgomery Modular Inverse Algorithm
Rui Deng
Yujie Zhou
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TC.2006.150
Send link to a friend
| Abstract |
|
After a comprehensive study on the Montgomery modular inverse algorithm and its revised versions, two modified high radix algorithms are proposed which utilize higher radix to reduce iterations needed without increasing complexity much, thereby accelerating the process. The radix-4 algorithm can reduce the average number of iterations from 1.4n to 0.82n and a software experiment shows the speedup is about 11 percent and iterations are 41.5 percent less on average. The radix-8 algorithm can reduce the average number of iterations to 0.73n, but it is more complicated, which makes it suitable only for very large numbers (2,048 bits) in the experiment, where the speedup can be 13--18 percent. The proposed algorithms are suitable for software implementations on general-purpose microprocessors.
|
 References
|
[1] B.S. Kaliski Jr., “The Montgomery Inverse and Its Applications,” IEEE Trans. Computers, vol. 44, no. 8, pp. 1064-1065, Aug. 1995.
[2] E. Savas and Ç.K. Koç, “The Montgomery Modular Inverse-Revisited,” IEEE Trans. Computers, vol. 49, no. 7, pp. 763-766, July 2000.
[3] A. Gutub, “A Scalable Hardware for Montgomery Modular Inverse Computation,” technical report, Information Security Laboratory, Electrical and Computer Eng. Dept., Oregon State Univ., Corvallis, June 2001.
[4] A. Gutub, A.F. Tenca, and Ç.K. Koç, “Scalable VLSI Architecture for GF(p) Montgomery Modular Inverse Computation,” Proc. IEEE CS Ann. Symp. VLSI, pp. 53-58, 2002.
[5] R. Lórencz, “New Algorithm for Classical Modular Inverse,” Proc. Fourth Int'l Workshop Cryptographic Hardware and Embedded Systems, revised papers, pp. 57-70, 2002.
[6] A.A.A. Gutub and A.F. Tenca, “Efficient Scalable Hardware Architecture for Montgomery Inverse Computation in GF(p),” Proc. IEEE Workshop Signal Proceesing Systems (SIPS '03), pp. 93-98, Aug. 2003.
[7] C. McIvor, M. McLoone, and J.V. McCanny, “Improved Montgomery Modular Inverse Algorithm,” IEEE Electronics Letters, vol. 40, no. 18, pp.1110-1112, Sept. 2004.
[8] A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography. CRC Press, 1996.
[9] D.E. Knuth, The Art of Computer Programming, volume 2, Seminumerical Algorithm, third ed. Reading, Mass.: Addison-Wesley, 1998.
[10] A.A.-A. Gutub, A.F. Tenca, E. Savas, and Ç.K. Koç, “Scalable and Unified Hardware to Compute Montgomery Inverse in $GF(p)$ and $GF(2^n)$ ,” Proc. Workshop Cryptography Hardware and Embedded Systems (CHES 2002), pp.484-499, Aug. 2002.
|
 Additional Information
|
Index Terms- Montgomery modular inverse, modular arithmetic, cryptography.
Citation:
Rui Deng, Yujie Zhou,
"Improvement to Montgomery Modular Inverse Algorithm,"
IEEE Transactions on Computers,
vol. 55,
no. 9,
pp. 1207-1210,
Sept.,
2006
|
|
RSS Feed