一个乘法逆元的计算方法

songls

以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
  m. ~. ^2 }1 S8 w3 \设 (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)
! `; O2 R, Q: D# ~, m+ O$ p4 s8 w   .
( O- M1 V, N5 s0 d! j   .
  .
3 @( y0 ^* c$ h( {9 A7 O  qm-1*rm≡qm (mod n)
上述等式相乘，得：
& |8 O  r4 L% E+ z, f  a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
( |% Z4 Q6 V  b3 s: h- C: f' N' i  a*(q1*q2*...*qm)≡rm (mod n)
9 B! t8 M5 W% E& k8 W( g% O  如果对qi(1≤i≤m)进行如下的限定:
+ U9 O- g* E  H2 N! R1 o/ D$ B   a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
   则 qm=±1
  即 a与q1*q2*...*qm互逆
  例 求28在299的逆
! f1 x8 `. x+ ~     28*11≡9 （mod 299）
: o4 Y. c; G" B, m9 A  R$ |     9*33≡-2  （mod 299）
/ f$ i7 K$ m: z1 K" g) r     -2*-150≡1 (mod 299)
  逆为:    11*33*-150≡-32 (mod 299)
; n; K, m3 [2 i% }$ k     28*-22≡-1 (mod 299)
' d' Z" W+ r; Z9 g1 R, o  O  但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
0 ?/ x6 W0 G* U/ s8 p9 W& U- Z 下面给出其中一个算法：
, c  x! b. [" f& Q- \# G, y0 x  1    输入a,n  
/ t' H$ e! ^& s. I% l0 q  2   resulte = 1   ; 保存逆的结果
  3   r=n/a+1      ; 保证 r*a>n
  4  q=r*a-n       ; 得到余数，该余数小于a
9 w: }+ E9 h4 s% H  5  resulte=(resulte*r)%n   
  6  if q=1  then  print(逆为: resulte) return  resulte
) {/ F4 x. Y! M/ e6 N2 J  7  if q=0 or q=a then  print(存在因子: a)  return a ;
  8  a=q
  9  goto 3
3 k  ~) O8 s6 ]- [
$ ~+ C( g0 ^. x6 S