一个乘法逆元的计算方法
以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m
a*r1≡q1 (mod n)
q1*r2≡q2 (mod n)
q2*r3≡q3 (mod n)
.
.
.
qm-1*rm≡qm (mod n)
上述等式相乘，得：
a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
a*(q1*q2*...*qm)≡rm (mod n)
如果对qi(1≤i≤m)进行如下的限定:
a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
则 qm=±1
即 a与q1*q2*...*qm互逆
例 求28在299的逆
28*11≡9 （mod 299）
9*33≡-2 （mod 299）
-2*-150≡1 (mod 299)
逆为: 11*33*-150≡-32 (mod 299)
28*-22≡-1 (mod 299)
但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
下面给出其中一个算法：
1 输入a,n
2 resulte = 1 ; 保存逆的结果
3 r=n/a+1 ; 保证 r*a>n
4 q=r*a-n ; 得到余数，该余数小于a
5 resulte=(resulte*r)%n
6 if q=1 then print(逆为: resulte) return resulte
7 if q=0 or q=a then print(存在因子: a) return a ;
8 a=q
9 goto 3
页:
[1]