数学建模社区-数学中国
标题:
一个乘法逆元的计算方法
[打印本页]
作者:
songls
时间:
2023-12-10 20:02
标题:
一个乘法逆元的计算方法
以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
; f! o* T, d* N& d
设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m
+ i$ I' N! k4 g$ k9 N4 W( v
a*r1≡q1 (mod n)
$ U9 v( a. z8 B% R( A0 e
q1*r2≡q2 (mod n)
L0 Y- K7 Y/ S+ V p/ |
q2*r3≡q3 (mod n)
/ I( ?& X" }7 d7 g
.
5 `' W9 ]# k3 n+ X, ^
.
* N* {3 a" i, [' K! H& }
.
Y. b, k2 X: @9 u" K1 g
qm-1*rm≡qm (mod n)
( {: z, |' A1 w3 [) Z! i& K0 ?& T
上述等式相乘，得：
. ?/ U! I; f! d! F
a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
! m6 v4 ^ l7 q# G6 [& t: g0 I
a*(q1*q2*...*qm)≡rm (mod n)
9 }9 `+ J0 {+ G, `- }/ E! e
如果对qi(1≤i≤m)进行如下的限定:
) L3 }5 c, i$ X5 e' T
a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
6 j# `& ~& e' }$ X/ {3 x
则 qm=±1
. O7 j& A/ L2 j# u/ a2 R
即 a与q1*q2*...*qm互逆
8 A2 G* x3 [% o* o( L9 `8 H2 I. w) N
例 求28在299的逆
- ?( t# Y- w+ a. U- @/ t
28*11≡9 （mod 299）
4 d: X& Y8 S* {' U7 c
9*33≡-2 （mod 299）
6 n( Z3 m0 C9 `( S
-2*-150≡1 (mod 299)
- z+ x7 G6 R3 Z# I q8 b! T
逆为: 11*33*-150≡-32 (mod 299)
1 u* V' x$ \ K/ d1 Y$ x
28*-22≡-1 (mod 299)
6 H) C7 o F1 }4 _+ H& @
但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
1 B% r- ^" n6 Q1 E% C! {) B
下面给出其中一个算法：
3 d9 t: T; g( i, _0 P( Z% l
1 输入a,n
3 n& h& [2 H' g9 ?$ {+ Z2 c3 y
2 resulte = 1 ; 保存逆的结果
7 X0 \* w4 Z; y9 {+ _" F
3 r=n/a+1 ; 保证 r*a>n
+ l; k `6 x& y3 d) l R) c
4 q=r*a-n ; 得到余数，该余数小于a
" @; m) \2 t3 n+ v
5 resulte=(resulte*r)%n
5 @* Y3 m! L$ O- B
6 if q=1 then print(逆为: resulte) return resulte
6 G6 s) F8 R2 v; N
7 if q=0 or q=a then print(存在因子: a) return a ;
- P% j4 l$ h6 }/ `& O
8 a=q
/ n: S# {( w( `5 _" T! q
9 goto 3
# ]9 S/ [, h5 _; J% B
( ?5 J, N7 M( r1 T+ O& M
一个求乘法逆元的方法.pdf
2023-12-10 20:01 上传
点击文件名下载附件
下载积分: 体力 -2 点
39.85 KB, 下载次数: 0, 下载积分: 体力 -2 点
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
