提问:
RSA 算法中的MOD运算疑问?
《加密与解密》书中第207页RSA算法的私钥计算公式如下:
d=e的负1次方mod((p-1)(q-1))
而后举例选取e=17 p=37 ,q=41
d=17的负1次方mod1440=593
我的问题是:
1、不知道593是怎样得出来的?
2、17的负1次方是17分之1吗?是17的反码吗?
3、mod是什么运算呢?是求余吗?
回答:
mod是求余运算符。
如果x与y的积除以z所得的余数为1,即xy = 1 (mod z),则称x和y对于模数z来说互为逆元,这种互为逆元的关系用符号表示为:
x = y的-1次方 (mod z)
x的-1次方 = y (mod z)
其中,-1次方只是个逆元的表示记号而已,是仿照以前的“倒数”的表示法,并非真的就是-1次方。
17 * 593 mod (37-1)(41-1) = 1
17 * 593 mod 1440 = 1
求逆元用扩展欧基里德算法,初等数论书都有讲。
========================
比如
(123456的17次)%(37*41)
%:mod运算,就是求余数,
如,5%3=2
7%6=1
m^n%(q*p)
其
中q,p是两个不相等的素数,一般使用的是时候都是选8位那么大的素数
常用的n有3、17、65537(2^16+1)……都是2的多少次+1
据
说这取这些数有简便方法,要是真直接算
1234^65537%(8503*9907)电脑非卡死不可,可是用人家给出的运算工具,非常快,我想知
道,有没有简便的方法。
8503*9907这两个素数取的已经是相当保守了
阅读(7812) | 评论(0) | 转发(0) |