数学建模社区-数学中国
标题:
一个乘法逆元的计算方法
[打印本页]
作者:
songls
时间:
2023-12-10 20:02
标题:
一个乘法逆元的计算方法
以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
$ G2 S- z. A0 h7 j0 ?
设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m
) j5 `9 q+ q, P( K1 t
a*r1≡q1 (mod n)
0 C P% E% C6 @; ~- k1 a
q1*r2≡q2 (mod n)
; v$ x! K8 Z3 _: ?8 x. \
q2*r3≡q3 (mod n)
8 | Z) R' s+ |# T! t
.
. x$ y& ?' r; K0 V
.
; l% B: O7 d. D6 {& h/ F- D3 E
.
8 s9 |2 B1 Q: `
qm-1*rm≡qm (mod n)
5 P' @ h! G H
上述等式相乘，得：
9 `- H. J" `$ Q4 {
a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
9 P; b! [2 `/ [) w' T1 ^% u1 Q3 N; Z. X
a*(q1*q2*...*qm)≡rm (mod n)
/ r* W* L& F0 [. \$ ^+ Y
如果对qi(1≤i≤m)进行如下的限定:
S" F3 [" w5 s1 k
a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
" M I* H% i1 j# V9 q% {
则 qm=±1
. Z' x+ P/ e5 B# O" B7 @3 Z
即 a与q1*q2*...*qm互逆
) b% J1 I: u4 c1 t* X! u0 K* V
例 求28在299的逆
0 T+ u8 A$ W9 K
28*11≡9 （mod 299）
; b3 p9 M8 ^4 Q, v
9*33≡-2 （mod 299）
$ E' }5 @* L6 X; t* U, k& w
-2*-150≡1 (mod 299)
( ^, u! M% F) h- C* ~+ F8 ?( ]
逆为: 11*33*-150≡-32 (mod 299)
+ s0 t4 T0 f5 T* `! g
28*-22≡-1 (mod 299)
/ v7 X8 Q0 O8 w9 H" O
但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
/ |0 P0 B3 i2 K0 K" J% H6 O$ P! U; I
下面给出其中一个算法：
+ {. c. Y7 r0 u) S. i. E
1 输入a,n
8 b8 B7 h& N0 l" R' t4 \* r
2 resulte = 1 ; 保存逆的结果
. r7 K' u$ G) m) h! S6 u- C
3 r=n/a+1 ; 保证 r*a>n
" c2 z$ Q! ^3 h! ]/ E7 A
4 q=r*a-n ; 得到余数，该余数小于a
% q2 X) R+ }0 n# {; L* S# F! {' Y
5 resulte=(resulte*r)%n
( t' l% J/ _ P% X
6 if q=1 then print(逆为: resulte) return resulte
+ s4 p7 o' O9 \! l3 F
7 if q=0 or q=a then print(存在因子: a) return a ;
% l/ Y8 p. V- q z# ]' Z7 E. o) X y" M9 p
8 a=q
8 w y9 J1 Z7 r& l' l
9 goto 3
3 `5 n! R3 r* i2 G1 v* W) n
' Q' o; d0 ~! ^
一个求乘法逆元的方法.pdf
2023-12-10 20:01 上传
点击文件名下载附件
下载积分: 体力 -2 点
39.85 KB, 下载次数: 0, 下载积分: 体力 -2 点
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
