THE MONTGOMERY INVERSE AND ITS APPLICATIONS

被引：108
作者：
KALISKI, BS
机构：
[1] RSA Laboratories, RSA Data Security, Inc., Redwood City, CA 94065, 100 Marine Parkway
来源：
IEEE TRANSACTIONS ON COMPUTERS | 1995年 / 44卷 / 08期
关键词：
D O I：
10.1109/12.403725
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
The Montgomery inverse of b module a is b(-1)2(n) mod a, where n is the number of bits in a. The right-shifting binary algorithm for modular inversion is shown naturally to compute the new inverse in fewer operations than the ordinary modular inverse. The new inverse facilitates recent work by Koc on modular exponentiation and has other applications in cryptography.
引用
收藏
页码：1064 / 1065
页数：2
相关论文
共 15 条
[1]  
DUSSE SR, 1990, ADV CRYPTOLOGY EUROC, P230
[2]   A PUBLIC KEY CRYPTOSYSTEM AND A SIGNATURE SCHEME BASED ON DISCRETE LOGARITHMS [J].
ELGAMAL, T .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1985, 31 (04) :469-472
[3]  
EVEN S, 1991, ADV CRYPTOLOGY 90, P619
[4]  
GUYOT A, 1991, 10TH IEEE SYMPOSIUM ON COMPUTER ARITHMETIC, P226, DOI 10.1109/ARITH.1991.145564
[5]  
Knuth D.E., 1981, ART COMPUTER PROGRAM, V2
[6]  
KOC CK, 1987, INT J COMPUT MATH, V40, P139
[7]  
Laurichesse D., 1991, Computers & Security, V10, P263, DOI 10.1016/0167-4048(91)90042-C
[8]  
MASSEY JL, 1993, FEB ADV TECHN SEM ZU
[9]  
MONTGOMERY PL, 1985, MATH COMPUT, V44, P519, DOI 10.1090/S0025-5718-1985-0777282-X
[10]  
PARIKH SN, 1991, 10TH IEEE SYMPOSIUM ON COMPUTER ARITHMETIC, P220, DOI 10.1109/ARITH.1991.145563
12