关于此问题的补充，如果乘法逆元不存在的情况如何解密 (1千字)
关于一个解密算法的解答(补充)作者 : zmworm
E-Mail: zmworm@sohu.com
HomePage: ZMWorm.Yeah.Net
刚才说的情况是 e'存在的情况，若e'不存在，应该怎样解密呢？
首先，我们要知道e满足什么条件时，e'存在。我们有以下定理：
如果gcd(e,f)=1(即 e,f 互素)，那么e有一个模f的乘法逆元。
[gcd(e,f)=p,表示e,f的最大公约数是p,求最大公约数可以用辗转相除法]
如果gcd(e,f)=p(p>1) 则 不存在e关于f的乘法逆元。
现在我们就求乘法逆元不存在时 K*e mod f=d 的解-----------------[e]
因为 gcd(e,f)=p 所以 p|e, p|f,设 e"=e/p ,f"=f/p ,m=K*e div f,则
K*e mod f=d => K*e=m*f+d => K*e"*p=m*f"*p+d => d=K*e"*p-m*f"*p=(K*e"-m*f")*p
所以 p|d, 令 d"=d/p ,则
K*e mod f=d => K*e"*p=m*f"*p+d"*p => K*e"=m*f"+d" => K*e" mod f"=d"
而 gcd(e",f")=1,这样我们就可以求e"的逆元e'
所以 d"*(e'*e") mod f"=d" =>d"*e'*e"*p mod f"*p=d"p
即 (d"*e')*e mod f=d -------------------------------------[f]
对比[e] [f] 有 K=d"*e'
注意 这只是K的一个解
事实上，Ki=d"*e'+(i-1)f" (i=1..p) 都满足条件, 因为 (d"*e'+if")*e" mod f"=d"
也就是说，若gcd(e,f)=p 则K有p个值
[例] 求 满足K*14 mod 96 =12中K的值
解 因为gcd(14,96)=2,所以k 有两个解
e"=14/2=7 f"=96/2=48 d"=12/2=6
7关于 48的逆元e'=7 (因为 7*7 mod 48 =1)
所以 Ki=d"*e'+(i-1)f"=6*7+（i-1)*48 (i=1,2)
解得 K1=42 K2=90
若不存在逆元的解密算法为
K1=:A2'*N1" mod A1
K2=:B2'*N2" mod B1
K3=:C2'*N3" mod C1
K4=:D2'*N4" mod D1
M1=(K1 xor A3 xor 0)
M2=(K2 xor B3 xor N1)
M3=(K3 xor C3 xor N2)
M4=(K4 xor D3 xor N3)
