数学建模社区-数学中国

标题: 一个乘法逆元的计算方法 [打印本页]

作者: songls    时间: 2023-12-10 20:02
标题: 一个乘法逆元的计算方法
以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。
- ]' y1 o8 P# G( {6 X( f: M设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m) k3 S1 H6 T5 A4 o: g
  a*r1≡q1 (mod n)
3 G" z$ j! y; y% ^$ n: f  q1*r2≡q2 (mod n), C4 w- u1 E, V2 g2 M/ K
  q2*r3≡q3 (mod n)
, @7 Y( ~4 J* K2 w7 o1 m$ v   .: x3 @; P% g* I5 _7 s' h
   .
- l% g& {8 F& P  D2 v  .6 L/ E, h4 s9 r5 J% A0 k! Y9 d, _- c) b
  qm-1*rm≡qm (mod n)
& H8 N# R/ M3 f( p5 ]8 O 上述等式相乘,得:
( S5 v0 K, o% E5 u  a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>7 y4 t0 V1 ?( ~" E
  a*(q1*q2*...*qm)≡rm (mod n) 3 t6 i5 z/ |- o4 p# @! ]7 u
  如果对qi(1≤i≤m)进行如下的限定:6 `. v& _. T$ w/ ?+ ]$ H: ~7 P& k
   a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
' T7 k- X( C7 ?# O* h* R   则 qm=±1$ o9 c2 f+ k# U: W  G: o
  即 a与q1*q2*...*qm互逆7 f& i" H" a, l6 C% a
  例 求28在299的逆+ p) ^. T8 O* S9 S! X4 d& R: `
     28*11≡9 (mod 299)) z6 G. v3 V( E5 m
     9*33≡-2  (mod 299)  |( B2 `  a/ i. Y0 f) e: }* B/ ]0 l
     -2*-150≡1 (mod 299)% ~1 i  L/ n8 f  [
  逆为:    11*33*-150≡-32 (mod 299)
. d0 a( [% w9 b2 H     28*-22≡-1 (mod 299)4 t3 V2 _3 q0 v
  但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。
6 L. [% G# Q' |  Q 下面给出其中一个算法:
) o" T: I% t* I; A: I  1    输入a,n  
  V" V. c& P9 U) G  d6 d/ I  2   resulte = 1   ; 保存逆的结果 * M& ]- R# X% c
  3   r=n/a+1      ; 保证 r*a>n4 C3 P% c: F* J* E4 f) U
  4  q=r*a-n       ; 得到余数,该余数小于a
; b1 s% w1 h+ W! Q1 x5 S, o  5  resulte=(resulte*r)%n   
: r  @8 _9 J7 p' P  6  if q=1  then  print(逆为: resulte) return  resulte
5 w6 _. m/ O4 N- O/ J2 W" c  7  if q=0 or q=a then  print(存在因子: a)  return a ;
1 \, e7 z1 n/ r/ p  8  a=q1 D3 u) A1 F% [9 U8 H: T  j  d
  9  goto 3
6 a. @0 _5 q: V+ F: n
- x+ G2 O4 y- I: g

一个求乘法逆元的方法.pdf

39.85 KB, 下载次数: 0, 下载积分: 体力 -2 点






欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5