一个乘法逆元的计算方法

songls

以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m
/ G4 |2 h4 o2 z# k) G8 P/ o- n  a*r1≡q1 (mod n)
  q1*r2≡q2 (mod n)
  q2*r3≡q3 (mod n)
5 n9 ?- c8 _4 J+ u   .
   .
  .
  qm-1*rm≡qm (mod n)
1 F- A0 V2 M0 f 上述等式相乘，得：
  a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
  a*(q1*q2*...*qm)≡rm (mod n)
  如果对qi(1≤i≤m)进行如下的限定:
   a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
5 [# |- z+ _5 l, v( A4 F   则 qm=±1
  即 a与q1*q2*...*qm互逆
6 g+ Y* D: i3 Z, Y  k( h9 e: C  例 求28在299的逆
- m% P# _  F, t3 Z( I* t     28*11≡9 （mod 299）
! {$ @+ m  p. s6 u) |     9*33≡-2  （mod 299）
& e+ X2 C2 B! Q6 [5 ^     -2*-150≡1 (mod 299)
/ L; s" }6 m/ e  K. u  逆为:    11*33*-150≡-32 (mod 299)
     28*-22≡-1 (mod 299)
  但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
; w. ^& a  ?3 d4 {9 J 下面给出其中一个算法：
8 D- E1 r% ~7 D' h! T% `5 |  1    输入a,n  
1 |0 I! X( w  J3 b4 G/ h  2   resulte = 1   ; 保存逆的结果
6 X7 j- s. U2 y$ k$ }3 i8 i  3   r=n/a+1      ; 保证 r*a>n
  4  q=r*a-n       ; 得到余数，该余数小于a
+ L5 g) u% [# f$ j$ [: J  5  resulte=(resulte*r)%n   
& s# S$ o3 {$ [/ c' [  6  if q=1  then  print(逆为: resulte) return  resulte
  7  if q=0 or q=a then  print(存在因子: a)  return a ;
  8  a=q
8 R0 Q$ y; X7 ^: O4 B# j- W6 E. N  9  goto 3