数学建模社区-数学中国

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

---

作者: songls    时间: 2023-12-10 20:02
标题: 一个乘法逆元的计算方法
以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m
% b, y  X8 B3 Z' N5 G- q  a*r1≡q1 (mod n)
  n+ g: @1 P& E  q1*r2≡q2 (mod n)
- T) R2 ?4 _0 r  q2*r3≡q3 (mod n)
8 G# a0 m- Z6 T' e5 ^) h8 U   .
   .
  .
  qm-1*rm≡qm (mod n)
6 r7 \. ^) x: t# X! N( z 上述等式相乘，得：
2 a' u4 d  u# @7 {# h  a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
) s1 G- \! X( l+ V) l# z  a*(q1*q2*...*qm)≡rm (mod n)
' T' N: L+ R, T. W9 j) Q  如果对qi(1≤i≤m)进行如下的限定:
/ l0 H/ k" n+ e, s   a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
* |5 J* H4 F# t# d% L, y   则 qm=±1
+ P" P( T% |0 j/ J+ U  即 a与q1*q2*...*qm互逆
# p& b- `. ^! s' j6 g4 L& v  例 求28在299的逆
     28*11≡9 （mod 299）
     9*33≡-2  （mod 299）
     -2*-150≡1 (mod 299)
  逆为:    11*33*-150≡-32 (mod 299)
1 R) X4 \2 E  [+ s$ M1 [( @     28*-22≡-1 (mod 299)
4 f; I- S, h% l) V5 t/ E  但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
下面给出其中一个算法：
  1    输入a,n  
! I5 J4 r! O% M  N4 E* o; o  2   resulte = 1   ; 保存逆的结果
  3   r=n/a+1      ; 保证 r*a>n
# r' c. f6 o- b! s1 M$ F5 j  4  q=r*a-n       ; 得到余数，该余数小于a
, Y, @; R  K( M% l; g; V' @8 c5 F4 w  5  resulte=(resulte*r)%n   
  6  if q=1  then  print(逆为: resulte) return  resulte
" O: T* }8 C: y& L7 c% V  7  if q=0 or q=a then  print(存在因子: a)  return a ;
* v) q% U" o0 H% T( b; n# q  8  a=q
! K1 Q: c# G/ B: 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