数学建模社区-数学中国
标题:
一个乘法逆元的计算方法
[打印本页]
作者:
songls
时间:
2023-12-10 20:02
标题:
一个乘法逆元的计算方法
以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
b- U4 E9 q$ q9 _
设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m
6 v# P6 L, i* p& t- f- y# c, l
a*r1≡q1 (mod n)
5 L( X) I; E3 X' ]
q1*r2≡q2 (mod n)
5 g& x0 u$ t0 \* X
q2*r3≡q3 (mod n)
: Z4 D z" M( c1 |' @3 c2 `
.
3 j. `7 n, f/ G2 n$ b" [! m5 i
.
' X- B d* n+ }3 ? W+ i. f
.
3 T3 a( h/ A" w
qm-1*rm≡qm (mod n)
( o/ `5 w$ D d- d
上述等式相乘，得：
! W6 o+ B8 t) S- M
a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
$ G& d! t* [: {" s1 a' [
a*(q1*q2*...*qm)≡rm (mod n)
- |) F' }, |, C) X' j+ U" I; A% _& T
如果对qi(1≤i≤m)进行如下的限定:
$ K0 y) o4 d. j0 B1 G! T8 @: T
a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
- ^ y9 N+ k6 X& f: `. a% S
则 qm=±1
1 _/ r: g, T0 D5 [- I& B
即 a与q1*q2*...*qm互逆
1 V1 q2 L# b, ]3 E# C
例 求28在299的逆
1 x: P4 c/ W) P: T u2 X; Q: l
28*11≡9 （mod 299）
5 E8 _2 J- f& F
9*33≡-2 （mod 299）
8 J( U% Z7 @- G5 B# q+ |2 v
-2*-150≡1 (mod 299)
$ U( m5 `4 a: z7 Y. F
逆为: 11*33*-150≡-32 (mod 299)
% V6 H8 J) S6 O! L# |* D4 E) I* _
28*-22≡-1 (mod 299)
* o4 j: ^% k0 B$ }
但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
/ C3 w5 U- b3 t# Y6 }! F, u
下面给出其中一个算法：
' H0 V l+ h4 H; Z5 b
1 输入a,n
" S2 C5 g/ [8 J% s' x, T
2 resulte = 1 ; 保存逆的结果
8 _3 J% F0 _; t9 G) N8 B" `
3 r=n/a+1 ; 保证 r*a>n
+ q( O! v8 X5 S% p
4 q=r*a-n ; 得到余数，该余数小于a
; V3 e+ b4 f" O9 X5 e2 t
5 resulte=(resulte*r)%n
1 N8 c$ w8 y0 [! H% j
6 if q=1 then print(逆为: resulte) return resulte
4 n5 q# z+ V4 X3 ]+ `
7 if q=0 or q=a then print(存在因子: a) return a ;
& w- q- M6 N7 p
8 a=q
1 L9 M" f' K) h! ?5 _3 J
9 goto 3
% v1 M/ F3 s# Y. c* R0 x
& ] [: a6 v/ Q. W
一个求乘法逆元的方法.pdf
2023-12-10 20:01 上传
点击文件名下载附件
下载积分: 体力 -2 点
39.85 KB, 下载次数: 0, 下载积分: 体力 -2 点
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
