数学建模社区-数学中国

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

作者: songls    时间: 2023-12-10 20:02
标题: 一个乘法逆元的计算方法
以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。
4 B+ I/ |1 h1 R' ]; n. M设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m* A5 X8 y  g% S" V3 a
  a*r1≡q1 (mod n)
5 p  a: A3 {+ I  K8 j  q1*r2≡q2 (mod n)! \# L: Z& z, l3 N1 ]9 P
  q2*r3≡q3 (mod n)
7 J  S# D5 U! G( d7 i* `2 _: r   .) T8 L/ H7 n% L7 R& L
   .% d% Q/ ]4 ]) T( H6 r0 s
  .$ n& c8 u- q! h* U5 |, \% t6 W1 t# P3 [
  qm-1*rm≡qm (mod n)
8 V8 Z, _& p8 q; Q 上述等式相乘,得:1 {* B9 U8 X$ e' l. \
  a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
4 f9 |9 {4 z# i( z  ~  a*(q1*q2*...*qm)≡rm (mod n)
' y# ?& h9 ]! _2 G  如果对qi(1≤i≤m)进行如下的限定:
  k' F/ l1 }, Y) p   a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|  v3 X% U' e# b  d' t
   则 qm=±15 @( v3 n" w( Z+ O9 U2 c
  即 a与q1*q2*...*qm互逆; {- q) R  |) p9 b. D% r3 R1 e
  例 求28在299的逆/ x4 j. s9 H8 C6 G- g7 t
     28*11≡9 (mod 299)
7 u/ b$ n" n$ r5 }     9*33≡-2  (mod 299)% a% J4 d5 J$ n
     -2*-150≡1 (mod 299)
5 |" D! m. g. D  逆为:    11*33*-150≡-32 (mod 299)
% v- v6 g, f# V$ d. |1 e5 h     28*-22≡-1 (mod 299)
" G8 W0 y0 v1 L0 I& u; D  但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。
) U. @; C9 S7 u& ^: [1 r/ u4 n 下面给出其中一个算法:7 S4 `/ h% m, K  g0 l. ~7 h
  1    输入a,n  
: D- Y/ [  l7 B+ U4 t  2   resulte = 1   ; 保存逆的结果 ) w. O; F/ n0 A% g: u4 _
  3   r=n/a+1      ; 保证 r*a>n
% w' [) g9 S' x, y! ]( N: n  4  q=r*a-n       ; 得到余数,该余数小于a1 p: b1 R+ \$ p1 ^) Z5 Q" w
  5  resulte=(resulte*r)%n   
7 D) P6 D% `, p0 ]$ w; o  6  if q=1  then  print(逆为: resulte) return  resulte
" i3 P6 F# C1 i( Y6 r9 _( ^  7  if q=0 or q=a then  print(存在因子: a)  return a ;
) n" f- U$ H, p  8  a=q
, r" F$ }* j* |& B, K  9  goto 3$ W/ b% D: a5 r# M
: G4 y- }; b  t

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

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






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