- 在线时间
- 7 小时
- 最后登录
- 2024-8-19
- 注册时间
- 2023-11-2
- 听众数
- 3
- 收听数
- 0
- 能力
- 0 分
- 体力
- 58 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 23
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 12
- 主题
- 6
- 精华
- 0
- 分享
- 0
- 好友
- 0
升级   18.95% TA的每日心情 | 郁闷 2023-12-11 09:00 |
|---|
签到天数: 7 天 [LV.3]偶尔看看II
 |
以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。: y' L- J$ [. y% p
设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m
0 u' Z* f9 |- B, L0 n W a*r1≡q1 (mod n); q: q1 |! u1 E
q1*r2≡q2 (mod n)
4 Q" w. _( j. B; Z$ v9 A: s$ L$ z- d q2*r3≡q3 (mod n): H; n+ Y& g% r( J9 \+ a" \4 m+ c
.! L6 Z$ \. u' y) }& L5 w
.3 _, u( Z3 u' H8 E3 K
.- I/ P" q1 u7 Y) {3 v
qm-1*rm≡qm (mod n), }/ v1 K) z1 E
上述等式相乘,得:9 c# C+ I, @* S! \
a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>* n. X' n4 \) Z. t
a*(q1*q2*...*qm)≡rm (mod n) ' \4 z% w" o* Z0 { V
如果对qi(1≤i≤m)进行如下的限定:
N4 r2 L; X9 M; U" ]6 j a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|) q! P6 u( Q9 |/ M: G
则 qm=±1
5 ?4 b3 x1 A1 I 即 a与q1*q2*...*qm互逆* C4 V6 Y' E9 J- @# s- ~3 T4 v b
例 求28在299的逆9 Y" B# i4 i* @$ ?1 ]/ s: b+ _3 _
28*11≡9 (mod 299)/ M+ H S$ b3 x
9*33≡-2 (mod 299)9 f) ?8 e& w: {1 q0 Y( R8 X" i
-2*-150≡1 (mod 299)
4 {' m. k7 V& J+ Y 逆为: 11*33*-150≡-32 (mod 299)
7 C& }( d2 Q/ C5 u" D, d1 d5 e 28*-22≡-1 (mod 299)
2 ?5 t0 f' L% w4 }- p2 I 但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。
" C# F3 \* t+ ]+ a 下面给出其中一个算法:
( ^$ Q& \. \1 p0 Y# x 1 输入a,n 9 _/ P/ W( r4 i. E8 u# C% [
2 resulte = 1 ; 保存逆的结果
" G. y1 a" X l& Q9 J5 v6 V- ~( h6 s: @ 3 r=n/a+1 ; 保证 r*a>n
* v6 s! [$ D* ~ 4 q=r*a-n ; 得到余数,该余数小于a
' h( ?, |, r$ ?9 P! ^4 S, b: ` 5 resulte=(resulte*r)%n
3 a3 b# `1 d- _7 W& U/ R 6 if q=1 then print(逆为: resulte) return resulte
4 a3 v' a, _& B# j, V! T 7 if q=0 or q=a then print(存在因子: a) return a ;
: h- s) |9 k5 F- s6 C 8 a=q
1 j7 A+ J2 ~ S( C9 x 9 goto 3
9 ]4 p( n7 v N( j: W
, c6 N3 v4 `) z4 Z |
zan
|