一个乘法逆元的计算方法

songls

以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
  o7 W- ~" O" H6 i$ U5 ]9 v设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m
. ^. p8 a5 Y6 `# U9 N7 p/ H: ^# ~  a*r1≡q1 (mod n)
6 V0 Q# e  k  l- h% o  q1*r2≡q2 (mod n)
$ n1 b7 e2 c  g+ G/ e3 h+ j2 Q  r  q2*r3≡q3 (mod n)
+ e' U7 a& V3 b2 p% E   .
( R3 n  u' G* ^1 g$ L9 B3 l' i4 n   .
  .
6 {; }2 z7 d5 ^7 o7 s# g& L8 T  qm-1*rm≡qm (mod n)
上述等式相乘，得：
, i; L' Z; l$ e* [2 ~8 y* B8 i4 t  a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
! i9 n0 d* D4 V% J1 n# L  a*(q1*q2*...*qm)≡rm (mod n)
& [. ~! ~" R& y  d, u  如果对qi(1≤i≤m)进行如下的限定:
   a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
   则 qm=±1
  即 a与q1*q2*...*qm互逆
5 O- ~; H; q1 P7 [  例 求28在299的逆
     28*11≡9 （mod 299）
     9*33≡-2  （mod 299）
7 D9 ~  e- e- P7 ~     -2*-150≡1 (mod 299)
  逆为:    11*33*-150≡-32 (mod 299)
     28*-22≡-1 (mod 299)
  但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
+ F/ h+ H6 [$ a9 n4 h, I 下面给出其中一个算法：
3 ^' B. o; H8 C5 N2 A8 p0 |  1    输入a,n  
  2   resulte = 1   ; 保存逆的结果
  3   r=n/a+1      ; 保证 r*a>n
  4  q=r*a-n       ; 得到余数，该余数小于a
, @5 ^" z4 A3 ?+ X6 y  5  resulte=(resulte*r)%n   
' l  T0 N7 i) \$ s  6  if q=1  then  print(逆为: resulte) return  resulte
  7  if q=0 or q=a then  print(存在因子: a)  return a ;
8 I4 M5 O9 f2 Z# T2 y/ Z7 u  8  a=q
  9  goto 3
& Z2 S! V  t' c* p4 B: y$ n