数学建模社区-数学中国
标题:
一个乘法逆元的计算方法
[打印本页]
作者:
songls
时间:
2023-12-10 20:02
标题:
一个乘法逆元的计算方法
以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。
z/ O X/ A, ~
设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m
% b, y X8 B3 Z' N5 G- q
a*r1≡q1 (mod n)
n+ g: @1 P& E
q1*r2≡q2 (mod n)
- T) R2 ?4 _0 r
q2*r3≡q3 (mod n)
8 G# a0 m- Z6 T' e5 ^) h8 U
.
K6 D) |" R2 }6 C' T9 J% Z
.
0 q6 N$ x0 w- x! @( D8 S. s% B* F3 F
.
* O" p; S7 W" Y/ h- j, z- W" ~
qm-1*rm≡qm (mod n)
6 r7 \. ^) x: t# X! N( z
上述等式相乘,得:
2 a' u4 d u# @7 {# h
a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
) s1 G- \! X( l+ V) l# z
a*(q1*q2*...*qm)≡rm (mod n)
' T' N: L+ R, T. W9 j) Q
如果对qi(1≤i≤m)进行如下的限定:
/ l0 H/ k" n+ e, s
a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
* |5 J* H4 F# t# d% L, y
则 qm=±1
+ P" P( T% |0 j/ J+ U
即 a与q1*q2*...*qm互逆
# p& b- `. ^! s' j6 g4 L& v
例 求28在299的逆
6 I% u* y! T! n7 s( ~
28*11≡9 (mod 299)
# S5 @( k& e* T( R
9*33≡-2 (mod 299)
7 ?/ E8 _* A5 G4 o
-2*-150≡1 (mod 299)
E y; b6 c9 ]. L3 i1 k; E4 v
逆为: 11*33*-150≡-32 (mod 299)
1 R) X4 \2 E [+ s$ M1 [( @
28*-22≡-1 (mod 299)
4 f; I- S, h% l) V5 t/ E
但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。
: L9 Y3 |5 ~: h( W0 X' s
下面给出其中一个算法:
: ?" _8 y- Z4 \+ D
1 输入a,n
! I5 J4 r! O% M N4 E* o; o
2 resulte = 1 ; 保存逆的结果
7 h4 d. A9 k6 m/ ]
3 r=n/a+1 ; 保证 r*a>n
# r' c. f6 o- b! s1 M$ F5 j
4 q=r*a-n ; 得到余数,该余数小于a
, Y, @; R K( M% l; g; V' @8 c5 F4 w
5 resulte=(resulte*r)%n
) _- f5 b' n! D8 y) G% I3 t
6 if q=1 then print(逆为: resulte) return resulte
" O: T* }8 C: y& L7 c% V
7 if q=0 or q=a then print(存在因子: a) return a ;
* v) q% U" o0 H% T( b; n# q
8 a=q
! K1 Q: c# G/ B: Q
9 goto 3
7 p0 n; w! s: e$ ?1 I1 [$ q& R: }
8 L3 N/ @7 }8 U! S5 }3 }! ]2 C. [+ F
一个求乘法逆元的方法.pdf
2023-12-10 20:01 上传
点击文件名下载附件
下载积分: 体力 -2 点
39.85 KB, 下载次数: 0, 下载积分: 体力 -2 点
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5