一个乘法逆元的计算方法

songls

以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
# N# D$ ^( o9 W设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m
  a*r1≡q1 (mod n)
  q1*r2≡q2 (mod n)
1 F# r- T+ r9 m; U  q2*r3≡q3 (mod n)
6 d/ q; T6 y1 N3 D/ S! \5 f8 i   .
/ j9 t# B% }( v" ~, k1 b1 V   .
6 ]" ], ]: |3 I( a! j  .
  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)
8 t2 _: S8 X6 S; h' w6 Q; ]  如果对qi(1≤i≤m)进行如下的限定:
: B7 ^+ }8 v2 x/ z# c. K0 ^   a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
' |3 K: `9 g" L& D   则 qm=±1
  即 a与q1*q2*...*qm互逆
  例 求28在299的逆
     28*11≡9 （mod 299）
5 G+ P) |+ s$ q& }5 z- h: P1 @     9*33≡-2  （mod 299）
     -2*-150≡1 (mod 299)
  逆为:    11*33*-150≡-32 (mod 299)
     28*-22≡-1 (mod 299)
- Y  K% c) D! Y1 I& a$ {8 E  但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
下面给出其中一个算法：
* J9 k. h( x8 c; @$ N, v! E( i9 y  1    输入a,n  
  2   resulte = 1   ; 保存逆的结果
( O$ c6 E0 |& b# _+ G, i. b  g/ e/ U  3   r=n/a+1      ; 保证 r*a>n
0 f+ t. R0 Q5 t) L6 h0 @  4  q=r*a-n       ; 得到余数，该余数小于a
+ X7 F: v3 H& ]4 T: n0 _( I  5  resulte=(resulte*r)%n   
  6  if q=1  then  print(逆为: resulte) return  resulte
2 ~! x4 [* j: H; i) S3 |8 j0 g0 t  7  if q=0 or q=a then  print(存在因子: a)  return a ;
  8  a=q
  9  goto 3
; X. S4 t' Y2 {& l1 y4 {+ a# }& |