一个乘法逆元的计算方法

songls

以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
+ {& @  v) A$ T& k& z设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m
* g) ?: x* n6 v" ^2 C7 U& N  I  a*r1≡q1 (mod n)
; H, l; O, {' e3 ~- l" L" n3 o  q1*r2≡q2 (mod n)
  q2*r3≡q3 (mod n)
9 g- u- X$ V9 K, q   .
6 A( Q; R9 |: ~5 Y/ X   .
; Y# Y8 z, R3 `/ z  .
  qm-1*rm≡qm (mod n)
% ?6 z' W8 E; x) h2 c1 ] 上述等式相乘，得：
  a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
7 u2 }- y: B% d5 R' H  a*(q1*q2*...*qm)≡rm (mod n)
  如果对qi(1≤i≤m)进行如下的限定:
1 t* B2 `5 k9 b1 [# t   a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
   则 qm=±1
# z: a0 Z7 y( a9 L. X8 w  即 a与q1*q2*...*qm互逆
! V: i. y6 h) v0 f  例 求28在299的逆
4 c5 \% F/ |; Q' i  ]     28*11≡9 （mod 299）
, v4 y* ?' U- e2 V3 J4 e2 u& W     9*33≡-2  （mod 299）
7 C0 ^% C) i/ @* d1 w, V     -2*-150≡1 (mod 299)
% H1 J* s, ~1 }3 Y5 q/ `6 @  逆为:    11*33*-150≡-32 (mod 299)
7 |! J# Y* \; @1 I$ i2 N     28*-22≡-1 (mod 299)
  但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
  x3 n( @" V1 [' }9 M0 [9 ~ 下面给出其中一个算法：
, c9 S8 O. w1 e: A8 a( Z  t  1    输入a,n  
  2   resulte = 1   ; 保存逆的结果
  3   r=n/a+1      ; 保证 r*a>n
  4  q=r*a-n       ; 得到余数，该余数小于a
! e7 r- T% \: A8 B& h8 ^  5  resulte=(resulte*r)%n   
; a, W# t1 M5 B( Y  6  if q=1  then  print(逆为: resulte) return  resulte
1 |% {+ g3 K' W0 P0 m; A, H( w  7  if q=0 or q=a then  print(存在因子: a)  return a ;
  8  a=q
1 f1 `9 {& z9 I; d: B* V  9  goto 3

$ `  V: J% o; W( }3 ?/ p8 N% c