数学建模社区-数学中国

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

---

作者: songls    时间: 2023-12-10 20:02
标题: 一个乘法逆元的计算方法
以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
% X7 d4 O, K* [. u设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m
& }2 ^* B, t& B2 ^- a( m  a*r1≡q1 (mod n)
( n8 L- P4 `/ [0 h& A2 Q  q1*r2≡q2 (mod n)
  q2*r3≡q3 (mod n)
" Y; s5 f% D( u  R  S  S- ~( R   .
   .
1 G8 {5 [1 s& T# R1 M$ n# [  .
  qm-1*rm≡qm (mod n)
5 v# x! r; l. [3 f1 X 上述等式相乘，得：
. S  \, H( }5 ~5 o' u0 `  a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
  a*(q1*q2*...*qm)≡rm (mod n)
3 _9 N4 s" U) ^  如果对qi(1≤i≤m)进行如下的限定:
# I- X$ O# o1 Q+ A; k   a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
   则 qm=±1
  即 a与q1*q2*...*qm互逆
6 }# L% `, j1 s5 r: |$ B+ @  例 求28在299的逆
8 l1 `6 d$ z% r7 i5 l     28*11≡9 （mod 299）
     9*33≡-2  （mod 299）
     -2*-150≡1 (mod 299)
  逆为:    11*33*-150≡-32 (mod 299)
     28*-22≡-1 (mod 299)
5 }5 K0 l) h! P0 K* e% @" S: f  但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
) _- E+ h7 D& `! t( Q0 ^  ^: O$ b- S 下面给出其中一个算法：
- c$ {5 W, S  K8 t7 E7 Q  1    输入a,n  
) |, G6 r% H' a8 a0 z5 c: O9 Q  2   resulte = 1   ; 保存逆的结果
  3   r=n/a+1      ; 保证 r*a>n
0 f% s- }/ f6 r) _  4  q=r*a-n       ; 得到余数，该余数小于a
  5  resulte=(resulte*r)%n   
  6  if q=1  then  print(逆为: resulte) return  resulte
  7  if q=0 or q=a then  print(存在因子: a)  return a ;
, d, r' Q1 _, S% p0 s4 f, Y  8  a=q
  9  goto 3

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

2023-12-10 20:01 上传

点击文件名下载附件

下载积分: 体力 -2 点

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

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5