数学建模社区-数学中国
标题:
一个乘法逆元的计算方法
[打印本页]
作者:
songls
时间:
2023-12-10 20:02
标题:
一个乘法逆元的计算方法
以下给出一个求乘法逆元的方法，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
- ]' y1 o8 P# G( {6 X( f: M
设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m
) k3 S1 H6 T5 A4 o: g
a*r1≡q1 (mod n)
3 G" z$ j! y; y% ^$ n: f
q1*r2≡q2 (mod n)
, C4 w- u1 E, V2 g2 M/ K
q2*r3≡q3 (mod n)
, @7 Y( ~4 J* K2 w7 o1 m$ v
.
: x3 @; P% g* I5 _7 s' h
.
- l% g& {8 F& P D2 v
.
6 L/ E, h4 s9 r5 J% A0 k! Y9 d, _- c) b
qm-1*rm≡qm (mod n)
& H8 N# R/ M3 f( p5 ]8 O
上述等式相乘，得：
( S5 v0 K, o% E5 u
a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
7 y4 t0 V1 ?( ~" E
a*(q1*q2*...*qm)≡rm (mod n)
3 t6 i5 z/ |- o4 p# @! ]7 u
如果对qi(1≤i≤m)进行如下的限定:
6 `. v& _. T$ w/ ?+ ]$ H: ~7 P& k
a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
' T7 k- X( C7 ?# O* h* R
则 qm=±1
$ o9 c2 f+ k# U: W G: o
即 a与q1*q2*...*qm互逆
7 f& i" H" a, l6 C% a
例 求28在299的逆
+ p) ^. T8 O* S9 S! X4 d& R: `
28*11≡9 （mod 299）
) z6 G. v3 V( E5 m
9*33≡-2 （mod 299）
|( B2 ` a/ i. Y0 f) e: }* B/ ]0 l
-2*-150≡1 (mod 299)
% ~1 i L/ n8 f [
逆为: 11*33*-150≡-32 (mod 299)
. d0 a( [% w9 b2 H
28*-22≡-1 (mod 299)
4 t3 V2 _3 q0 v
但该方法有个最大的问题，当(qi,n)>1时，该方法将无法继续往下计算逆。
6 L. [% G# Q' | Q
下面给出其中一个算法：
) o" T: I% t* I; A: I
1 输入a,n
V" V. c& P9 U) G d6 d/ I
2 resulte = 1 ; 保存逆的结果
* M& ]- R# X% c
3 r=n/a+1 ; 保证 r*a>n
4 C3 P% c: F* J* E4 f) U
4 q=r*a-n ; 得到余数，该余数小于a
; b1 s% w1 h+ W! Q1 x5 S, o
5 resulte=(resulte*r)%n
: r @8 _9 J7 p' P
6 if q=1 then print(逆为: resulte) return resulte
5 w6 _. m/ O4 N- O/ J2 W" c
7 if q=0 or q=a then print(存在因子: a) return a ;
1 \, e7 z1 n/ r/ p
8 a=q
1 D3 u) A1 F% [9 U8 H: T j d
9 goto 3
6 a. @0 _5 q: V+ F: n
- x+ G2 O4 y- I: g
一个求乘法逆元的方法.pdf
2023-12-10 20:01 上传
点击文件名下载附件
下载积分: 体力 -2 点
39.85 KB, 下载次数: 0, 下载积分: 体力 -2 点
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
