数学建模社区-数学中国
标题:
一个乘法逆元的计算方法
[打印本页]
作者:
songls
时间:
2023-12-10 20:02
标题:
一个乘法逆元的计算方法
以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
( Q) t- X0 t+ x, _
设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m
5 A. N" G9 X3 L* t& ?
a*r1≡q1 (mod n)
$ G2 h! w9 _- r/ c ~+ f
q1*r2≡q2 (mod n)
+ t0 Q$ d+ Y1 V
q2*r3≡q3 (mod n)
6 ?; n/ B# i' I z# L. A: U( e7 z4 b
.
* ?+ q$ D, E( A! j1 e& Z) q
.
' V* V9 [! j9 B; ~- M
.
8 K# w. C& ^1 o9 Q
qm-1*rm≡qm (mod n)
5 A0 w7 L x" S1 J3 c3 t
上述等式相乘，得：
# G9 G4 M2 x3 X6 i- C7 `4 {
a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
6 I. r+ D ]5 ^4 X. T( _- A
a*(q1*q2*...*qm)≡rm (mod n)
8 A( R5 }! Y* P) b9 |' R
如果对qi(1≤i≤m)进行如下的限定:
^( C! A( ?- P5 C
a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
3 {) s1 H* ^8 _! b) O r
则 qm=±1
0 b! _4 C! m% D, R t' D, j# E# C
即 a与q1*q2*...*qm互逆
2 i1 R& d. Y9 Q3 \# Q
例 求28在299的逆
" ~( n/ E/ f% x$ z1 o
28*11≡9 （mod 299）
% N# |, c0 w& ~* [* p) d
9*33≡-2 （mod 299）
) c6 x( F1 p: ^6 s2 ^. q9 B/ P
-2*-150≡1 (mod 299)
9 J* J4 {/ q* {0 R! ?/ K3 P0 c- V
逆为: 11*33*-150≡-32 (mod 299)
8 M. \2 D" \7 T+ m0 ~# s
28*-22≡-1 (mod 299)
1 [5 [ \* N' B) B" h- T
但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
) m7 q# V7 p# z- e
下面给出其中一个算法：
- c3 C1 B n( B% G, ]6 D: P
1 输入a,n
3 M7 q. ^# \8 o2 C3 \* `
2 resulte = 1 ; 保存逆的结果
# N$ P& m, `' G
3 r=n/a+1 ; 保证 r*a>n
( ]( _9 ^$ R2 O+ s
4 q=r*a-n ; 得到余数，该余数小于a
/ _( {- ^! F4 y$ Q3 _9 A2 r
5 resulte=(resulte*r)%n
6 b6 ^0 l8 o7 P# q: w1 ]
6 if q=1 then print(逆为: resulte) return resulte
0 U9 X$ ~7 R. f
7 if q=0 or q=a then print(存在因子: a) return a ;
8 C8 |0 B. C$ T; [( [% W
8 a=q
" W: `* j$ z: C& \
9 goto 3
4 d5 P! M: o4 @ ~% B
2 h: Q) z5 @; F T
一个求乘法逆元的方法.pdf
2023-12-10 20:01 上传
点击文件名下载附件
下载积分: 体力 -2 点
39.85 KB, 下载次数: 0, 下载积分: 体力 -2 点
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
