一个乘法逆元的计算方法

songls

以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
8 f% V3 ]8 z5 C  X7 c设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m
' l1 \5 ^2 m3 w- v  a*r1≡q1 (mod n)
& O2 J& P( z( B4 w+ i( R5 x  q1*r2≡q2 (mod n)
; r0 R7 h' h- s9 t5 L  q2*r3≡q3 (mod n)
   .
5 J2 }( S2 W; p, P8 H. m   .
  .
! U  S8 ?0 j) {) J  qm-1*rm≡qm (mod n)
上述等式相乘，得：
6 b1 L6 u9 g# _; k  a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
2 [0 C/ d* H. c1 W7 i0 c( Y( i  a*(q1*q2*...*qm)≡rm (mod n)
. D1 O9 E4 `9 p0 H3 h  如果对qi(1≤i≤m)进行如下的限定:
   a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
   则 qm=±1
) D  p6 S* t. H6 t0 ~. J  即 a与q1*q2*...*qm互逆
  例 求28在299的逆
6 ]* U+ l: G7 J; m  ^: Q     28*11≡9 （mod 299）
* d. j; d- N7 {. `     9*33≡-2  （mod 299）
     -2*-150≡1 (mod 299)
  逆为:    11*33*-150≡-32 (mod 299)
$ ]/ W4 K+ M  Y8 [     28*-22≡-1 (mod 299)
& Z2 Q; u' a) P  q! ]  ~/ V  但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
下面给出其中一个算法：
( G& ~8 g( ?7 s0 A6 h  1    输入a,n  
  2   resulte = 1   ; 保存逆的结果
4 H. _* @6 e# @' {' p  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
1 K1 n+ K6 u9 r" @, i  7  if q=0 or q=a then  print(存在因子: a)  return a ;
" s/ M; J6 g7 H3 F" R5 g  8  a=q
  9  goto 3

& C6 I1 B2 T! I! x; D: e6 @% [