一个乘法逆元的计算方法

songls

以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m
, m! M5 W8 V7 B6 K  a*r1≡q1 (mod n)
+ g/ r; s2 F9 V- q) e  q1*r2≡q2 (mod n)
  q2*r3≡q3 (mod n)
   .
2 y+ ~# W( {, A, G   .
" v4 r) m. S4 G. Q  .
  qm-1*rm≡qm (mod n)
( g0 x* X& P8 {- T. ]& V0 i5 O6 A 上述等式相乘，得：
  a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
  a*(q1*q2*...*qm)≡rm (mod n)
1 y  K2 A7 Y3 \: M4 w  如果对qi(1≤i≤m)进行如下的限定:
$ N& \  e. s8 z* ~5 y$ T   a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
0 _( P6 t9 \( W, ?! A# S, f- A1 b   则 qm=±1
( L6 x7 }& C2 [. k  j  即 a与q1*q2*...*qm互逆
  例 求28在299的逆
' l& x6 C1 R8 B5 ]     28*11≡9 （mod 299）
     9*33≡-2  （mod 299）
     -2*-150≡1 (mod 299)
6 u/ s8 A+ ^/ m: ]: p4 z+ c' X/ M0 h  逆为:    11*33*-150≡-32 (mod 299)
     28*-22≡-1 (mod 299)
  但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
  l  w! g! k6 ]. ^4 o 下面给出其中一个算法：
4 l  I. ]) {: f' z9 k' ^* b7 S* u  1    输入a,n  
  2   resulte = 1   ; 保存逆的结果
8 G6 R7 y& N! e6 L* t; {4 I  3   r=n/a+1      ; 保证 r*a>n
! ?1 |9 f$ L# N; Q2 b  4  q=r*a-n       ; 得到余数，该余数小于a
9 C8 C; M5 x& ]$ N  5  resulte=(resulte*r)%n   
' @, D2 C2 Q  Q5 N) ?  6  if q=1  then  print(逆为: resulte) return  resulte
  7  if q=0 or q=a then  print(存在因子: a)  return a ;
1 h0 {8 B8 X6 R- t* w$ H+ v; n! i) H  8  a=q
' ?' Q# m, n# b2 m& a  9  goto 3
1 r5 X4 e" `5 v6 m- |. M8 |, p4 S1 T
3 P. Y$ R* R) k# v