加密解密 中 简单的RSA计算 （主要是简单数论知识）

来源：百度知道 编辑：UC知道 时间：2024/07/07 20:46:34
p=101 q=113 选e=3533

N=PQ=11413
n=N(p-1)(q-1)=11200

ed≡1(mod11200)
3533d≡(1mod11200)
d=?
要求解过程

就是解同余方程 3533d≡1(mod 11200) 啰！
用辗转相除法就可以了。
11200x≡-1(mod 3533) ←→ 601x≡-1(mod 3533)
3533y≡1(mod 601) ←→ -73y≡1(mod 601) ←→ 73y≡-1(mod 601)
601z≡1(mod 73) ←→ 17z≡1(mod 73)
73u≡-1(mod 17) ←→ 5u≡-1≡16(mod 17)
取u=10，倒推回去：
z=(73*u+1)/17=43
y=(601*z-1)/73=354
x=(3533*y-1)/601=2081
d=(11200*x+1)/3533=6597
简单吧！

d=6597
解同余方程3533*d=11200*x+1 用计算器解得d=6597,x=2082