数学建模社区-数学中国
标题:
一个乘法逆元的计算方法
[打印本页]
作者:
songls
时间:
2023-12-10 20:02
标题:
一个乘法逆元的计算方法
以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
6 V ?% f& X1 W' Q7 @, ^
设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m
. k3 u9 R2 }) U: y) A( A
a*r1≡q1 (mod n)
+ p% U% M0 O% j$ c! P2 ~- g1 g: g
q1*r2≡q2 (mod n)
1 i$ p1 S0 F0 a
q2*r3≡q3 (mod n)
{# R, `( |+ O7 ^5 P5 j1 T
.
D4 k" Q0 d8 x1 Y! N; V5 C0 j
.
+ S3 R: X6 n# k% D
.
* m5 c* z+ ^% g$ X8 i7 x/ ~; Y! [
qm-1*rm≡qm (mod n)
' _& x4 @8 p2 V$ e1 _5 s1 a
上述等式相乘，得：
! V6 b7 A9 V4 u' {2 K( U9 G7 Q
a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
( d& i8 E/ d, ^
a*(q1*q2*...*qm)≡rm (mod n)
! g3 d1 ~: }. l' A" b
如果对qi(1≤i≤m)进行如下的限定:
7 w, p( ?3 u+ @
a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
8 K0 M/ G; O2 ?3 Y7 T F
则 qm=±1
% u, n' |! c6 I4 l& j6 a
即 a与q1*q2*...*qm互逆
4 T4 @8 `' y, [! ]( ~7 o
例 求28在299的逆
& [% d& t( A9 O
28*11≡9 （mod 299）
. b7 `5 G+ V) H# j
9*33≡-2 （mod 299）
5 a2 w9 ^7 o: G7 ~; t4 {0 b) q' t
-2*-150≡1 (mod 299)
3 B" M9 r5 `5 ]# g
逆为: 11*33*-150≡-32 (mod 299)
6 l$ w( n( R! n6 K2 y9 E% C
28*-22≡-1 (mod 299)
( G9 F! G- d7 O
但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
1 _+ v- |8 ~6 P( S' {0 s) a
下面给出其中一个算法：
# z8 b! P) Z; t7 U2 D' `0 c' ]
1 输入a,n
( r5 ]* _- W! _; O# u
2 resulte = 1 ; 保存逆的结果
* S% n! i% @) M& ~: x
3 r=n/a+1 ; 保证 r*a>n
* Z, C* \0 p( p: G9 J
4 q=r*a-n ; 得到余数，该余数小于a
" Q. X' Q3 Q" K5 g
5 resulte=(resulte*r)%n
0 c; P: x l1 t$ R& H; X0 ?% A
6 if q=1 then print(逆为: resulte) return resulte
7 ?- \7 n: x C b
7 if q=0 or q=a then print(存在因子: a) return a ;
- {1 u0 Y& Z7 k% ^& m* f1 j
8 a=q
* f1 e- Y- P9 d6 y4 M3 t
9 goto 3
! I3 F% C* l5 w" `
8 q" i4 R+ h& B8 D4 K
一个求乘法逆元的方法.pdf
2023-12-10 20:01 上传
点击文件名下载附件
下载积分: 体力 -2 点
39.85 KB, 下载次数: 0, 下载积分: 体力 -2 点
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
