- 在线时间
- 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
 |
以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。! D+ |( c0 E$ N
设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m/ o. [& u9 [; \4 o
a*r1≡q1 (mod n)
& v2 F' ~) n9 A: d3 H; O q1*r2≡q2 (mod n)0 |2 I# @2 J6 P i
q2*r3≡q3 (mod n)" [$ p: y" x3 m2 `5 c
.
5 @+ C6 N% m# L- N5 k ./ n: }, H! g& P" q0 C5 d
.; a' _) m0 e4 A) O( R( E7 M
qm-1*rm≡qm (mod n)
7 S* J8 a) X' C2 ?" w* I 上述等式相乘,得:: @# i% b# {/ A2 c: ~7 a
a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
6 o, Q5 s* R: f1 ` a*(q1*q2*...*qm)≡rm (mod n)
: H; h8 v- q6 \0 c3 W 如果对qi(1≤i≤m)进行如下的限定:
8 n# `6 ]2 O) C7 n8 B a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
! }/ W1 V/ B' d 则 qm=±1
+ U* d9 z, m2 s) ~- r 即 a与q1*q2*...*qm互逆
8 I+ i+ ]/ ?* _/ ` 例 求28在299的逆
7 T3 K9 s4 F5 A3 A/ W6 T 28*11≡9 (mod 299)2 D. O& g- d% y$ O9 u. [6 W
9*33≡-2 (mod 299)+ W' H# D: H" Y- P5 u% @0 \+ [. F
-2*-150≡1 (mod 299)
0 F( [3 U8 Q# w$ ^* R 逆为: 11*33*-150≡-32 (mod 299)
' f8 e' V" M1 I) W5 W 28*-22≡-1 (mod 299)
+ ~+ e, c- ]& c/ j6 h+ s 但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。
& m: H& g) z7 G, f 下面给出其中一个算法:. J! J0 d8 P5 H7 J! h4 `
1 输入a,n
$ U8 v2 l' n& m' Q5 T1 a# { n 2 resulte = 1 ; 保存逆的结果 ( |* N% w6 P1 V% ^" Y
3 r=n/a+1 ; 保证 r*a>n
7 L! \6 L5 h6 e+ e2 O3 j 4 q=r*a-n ; 得到余数,该余数小于a
6 C# C% O+ s$ M- i 5 resulte=(resulte*r)%n " T( f3 ~$ I( [$ ^& w- ^5 E5 p: ]
6 if q=1 then print(逆为: resulte) return resulte
: X: P: {: v$ C 7 if q=0 or q=a then print(存在因子: a) return a ;/ A5 [0 n' X1 m7 Z8 `( q X1 s
8 a=q" h1 `( l1 i9 w
9 goto 32 {& C4 {( a5 v! h
8 b; Y7 ~ [! x( v3 Q9 ~ |
zan
|