数学建模社区-数学中国
标题:
一个乘法逆元的计算方法
[打印本页]
作者:
songls
时间:
2023-12-10 20:02
标题:
一个乘法逆元的计算方法
以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
7 V! X5 s: P' P
设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m
# z4 g6 [. W6 D2 p" T
a*r1≡q1 (mod n)
. P$ ]/ p- Q d! H# G/ k8 S
q1*r2≡q2 (mod n)
" E& U7 C3 g( h: k) S1 L
q2*r3≡q3 (mod n)
, Z* f, d& l. d9 G
.
2 |! X) ?' @! B
.
/ i' K2 V* ?3 {1 T
.
8 M2 P# z2 E& Y# @& k# |* a
qm-1*rm≡qm (mod n)
1 B0 n9 N5 N% ]
上述等式相乘，得：
9 y7 I1 T2 {' [2 e3 B
a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
# J% x! c7 \( v4 r+ N
a*(q1*q2*...*qm)≡rm (mod n)
3 t" Y6 C2 Q; N7 z+ T
如果对qi(1≤i≤m)进行如下的限定:
' H. a1 |/ }7 j
a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
0 w( N O! Q7 G- ~; d( {
则 qm=±1
, |8 A" ^) P- z- ]7 x( m
即 a与q1*q2*...*qm互逆
: u! C; C$ W6 E) z" W- N
例 求28在299的逆
9 T& N7 i3 e0 J
28*11≡9 （mod 299）
* t( g0 f9 u& k- ?6 k8 Z. p9 v
9*33≡-2 （mod 299）
7 V. e0 W& }7 J
-2*-150≡1 (mod 299)
0 j- z- h0 I0 T" z# H: [8 G7 J" B3 c
逆为: 11*33*-150≡-32 (mod 299)
7 ]2 D1 b, D- K+ j# ]1 w4 j, l
28*-22≡-1 (mod 299)
; ?% }% B3 M& W1 Z, H+ V8 m' K, d2 G% a
但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
, N( O# }, b/ L h0 W# k7 N4 w
下面给出其中一个算法：
& E; w6 w2 Y, s' R; g0 \, J* O, |
1 输入a,n
+ i6 x* M, j$ |2 q7 O
2 resulte = 1 ; 保存逆的结果
" m8 h, h9 S: x% V. V
3 r=n/a+1 ; 保证 r*a>n
" E4 b0 ~. @& ^' s" w# P7 @
4 q=r*a-n ; 得到余数，该余数小于a
2 A- s2 N" c. P4 \: T7 X6 _
5 resulte=(resulte*r)%n
6 x% u$ d' ^, _3 x0 d
6 if q=1 then print(逆为: resulte) return resulte
9 i1 D Y4 H, h, m2 y6 R
7 if q=0 or q=a then print(存在因子: a) return a ;
# U& \. O( M; D0 p1 p
8 a=q
! o9 V5 a q @7 l2 E5 ^. M/ A( x
9 goto 3
9 B" |! |3 ?: z3 @: N% m
* a6 V, W( o/ ~6 ]
一个求乘法逆元的方法.pdf
2023-12-10 20:01 上传
点击文件名下载附件
下载积分: 体力 -2 点
39.85 KB, 下载次数: 0, 下载积分: 体力 -2 点
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
