题目

RSA算法中的数学公式看不懂.想麻烦您 d=e^-1 三 1019(mod 3220) 这个e逆是怎么求的呢?烦劳您帮我看看.
RSA算法举例：比如,
1.选择素数 p = 47,q = 71,得 n = 3337,
2.中(n) = (p-1)(q-1) = 46 X 70 = 3220,
3.选择e = 79 ,得到私钥
d=e^-1 三 1019(mod 3220) 这个e逆是怎么求的呢?烦劳您帮我看看.

提问时间：2021-04-01

答案

e的逆可以按照辗转相除法,或者欧几里德定理计算啊.
3220=79*40+60
79=60*1+19
60=19*3+3
19=3*6+1
1=19*19-60*6=(79-60)*19-60*6=79*19-60*19-60*6=79*19-60*25=79*19-(3220-79*40)*25=79*19-3220+79*40*25=1019*79-3220
所以79 mod 3220 的逆就是1019