数学建模社区-数学中国
标题:
一个乘法逆元的计算方法
[打印本页]
作者:
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=±1
5 @( 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 ; 得到余数，该余数小于a
1 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
2023-12-10 20:01 上传
点击文件名下载附件
下载积分: 体力 -2 点
39.85 KB, 下载次数: 0, 下载积分: 体力 -2 点
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
