一个乘法逆元的计算方法

songls

以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
- t" Y7 q1 G2 V4 n! y3 C+ ^4 ~设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m
5 c: c/ v" R1 q' V, F, c( @/ {  a*r1≡q1 (mod n)
  q1*r2≡q2 (mod n)
  q2*r3≡q3 (mod n)
" Y9 H# {: P1 t" f  h   .
   .
  .
  qm-1*rm≡qm (mod n)
1 c% s) @3 p( e( [. _2 F 上述等式相乘，得：
* L2 G$ S4 B) A' ^  a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
  a*(q1*q2*...*qm)≡rm (mod n)
+ H, V2 m- g3 I/ F7 ^/ G  如果对qi(1≤i≤m)进行如下的限定:
1 n7 b, q! c6 @3 {5 s4 d4 t  ~   a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
( R* n8 l1 W) ^6 Q. h8 t   则 qm=±1
0 e+ J' t# D: y9 R2 i  即 a与q1*q2*...*qm互逆
  例 求28在299的逆
4 ~8 p" t& c* G8 U7 l" z     28*11≡9 （mod 299）
) w8 \- A  a0 A" J6 O: g     9*33≡-2  （mod 299）
' E6 I' Q" G5 C( T8 c     -2*-150≡1 (mod 299)
  逆为:    11*33*-150≡-32 (mod 299)
/ t& N8 p3 `0 g! H5 C     28*-22≡-1 (mod 299)
1 x5 [0 x1 s4 V7 n* _- G& x5 g  但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
下面给出其中一个算法：
  1    输入a,n  
7 J8 X6 Y# [% I; B. Q3 T" A! W' F) m. E  2   resulte = 1   ; 保存逆的结果
$ ^$ ~: J3 K5 X2 K  3   r=n/a+1      ; 保证 r*a>n
  4  q=r*a-n       ; 得到余数，该余数小于a
  5  resulte=(resulte*r)%n   
' N& _  ]( T2 z8 ?% M3 D5 L2 B  6  if q=1  then  print(逆为: resulte) return  resulte
  7  if q=0 or q=a then  print(存在因子: a)  return a ;
7 J$ U* k9 a5 e# O* @- c' n  8  a=q
1 h7 v1 n; W& D7 |9 E7 o  9  goto 3
. n/ X9 |* t! J: {8 o
) i- t! O) U% `' {0 P6 i' W! U