一个乘法逆元的计算方法

songls

以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
3 x' f; |5 N. Q设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m
  a*r1≡q1 (mod n)
# Y2 S* Q, Q3 W# ^4 u8 V% o  q1*r2≡q2 (mod n)
7 M, j' s- j2 H. U; r0 d& F  q2*r3≡q3 (mod n)
* w+ t+ A% V: c3 h   .
   .
' p8 F4 }$ C/ f6 e& N! i* w9 Y2 D  .
  qm-1*rm≡qm (mod n)
上述等式相乘，得：
( m+ v; h" q! G  a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
* B; J$ ^. P1 F6 `6 d! D! r, b1 j  a*(q1*q2*...*qm)≡rm (mod n)
3 ~3 h: ^( u9 a6 {  如果对qi(1≤i≤m)进行如下的限定:
3 ]9 P. e5 [5 i; r/ D  K   a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
0 K, I/ a7 c4 I& ^$ U3 S   则 qm=±1
) I# {1 l; y$ }. L9 X7 F  即 a与q1*q2*...*qm互逆
  例 求28在299的逆
     28*11≡9 （mod 299）
     9*33≡-2  （mod 299）
: c0 Q( ^( T+ a4 M8 E$ u0 r8 |3 H     -2*-150≡1 (mod 299)
. W6 z, e3 U: M  l  逆为:    11*33*-150≡-32 (mod 299)
     28*-22≡-1 (mod 299)
  但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
下面给出其中一个算法：
  1    输入a,n  
  2   resulte = 1   ; 保存逆的结果
2 c( g" Z' J8 g8 `) _. ^  3   r=n/a+1      ; 保证 r*a>n
  4  q=r*a-n       ; 得到余数，该余数小于a
% a3 G1 [2 a% E* c3 W% |  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 ;
5 X5 ~" {5 e0 U+ k  8  a=q
9 ]4 R; G6 e7 }$ ^- T6 y" l" [/ G4 j  9  goto 3
$ F3 m1 R3 k3 _( O