- 在线时间
- 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
 |
以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。
o7 W- ~" O" H6 i$ U5 ]9 v设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m
. ^. p8 a5 Y6 `# U9 N7 p/ H: ^# ~ a*r1≡q1 (mod n)
6 V0 Q# e k l- h% o q1*r2≡q2 (mod n)
$ n1 b7 e2 c g+ G/ e3 h+ j2 Q r q2*r3≡q3 (mod n)
+ e' U7 a& V3 b2 p% E .
( R3 n u' G* ^1 g$ L9 B3 l' i4 n . _6 P; z! G, c/ W& ~
.
6 {; }2 z7 d5 ^7 o7 s# g& L8 T qm-1*rm≡qm (mod n)9 ~# F3 @5 d" o& L& S6 |' q
上述等式相乘,得:
, i; L' Z; l$ e* [2 ~8 y* B8 i4 t a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
! i9 n0 d* D4 V% J1 n# L a*(q1*q2*...*qm)≡rm (mod n)
& [. ~! ~" R& y d, u 如果对qi(1≤i≤m)进行如下的限定:9 _. q) `: S+ q2 ^0 E" c( I
a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|& A' R$ `4 l; P6 B8 M
则 qm=±1; y1 r# g& ^) S+ z
即 a与q1*q2*...*qm互逆
5 O- ~; H; q1 P7 [ 例 求28在299的逆# J0 } N9 `9 c( p% E
28*11≡9 (mod 299)/ J9 {9 E" T" m# l
9*33≡-2 (mod 299)
7 D9 ~ e- e- P7 ~ -2*-150≡1 (mod 299)- J' T7 L' j; {# R
逆为: 11*33*-150≡-32 (mod 299)7 N9 K4 a8 f/ X) V- ?: _
28*-22≡-1 (mod 299)! B$ A2 d2 X$ R% _3 Z
但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。
+ F/ h+ H6 [$ a9 n4 h, I 下面给出其中一个算法:
3 ^' B. o; H8 C5 N2 A8 p0 | 1 输入a,n 9 ?) n* C4 I; k Y5 _
2 resulte = 1 ; 保存逆的结果 6 Q8 I) J+ r" S: {
3 r=n/a+1 ; 保证 r*a>n+ o, w4 Q+ i e# |( y# E
4 q=r*a-n ; 得到余数,该余数小于a
, @5 ^" z4 A3 ?+ X6 y 5 resulte=(resulte*r)%n
' l T0 N7 i) \$ s 6 if q=1 then print(逆为: resulte) return resulte" k9 L+ q5 M1 u& u2 \
7 if q=0 or q=a then print(存在因子: a) return a ;
8 I4 M5 O9 f2 Z# T2 y/ Z7 u 8 a=q1 U- @4 B5 e9 T
9 goto 3
& Z2 S! V t' c* p4 B: y$ n# S) J& X8 [: t' t0 Z8 x
|
zan
|