- 在线时间
- 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
 |
以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。
# N# D$ ^( o9 W设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m% F0 ^" d8 g9 w: D5 o `) \8 u
a*r1≡q1 (mod n)7 Q! H% h- B& C/ M) W. _; K) u. D7 y
q1*r2≡q2 (mod n)
1 F# r- T+ r9 m; U q2*r3≡q3 (mod n)
6 d/ q; T6 y1 N3 D/ S! \5 f8 i .
/ j9 t# B% }( v" ~, k1 b1 V .
6 ]" ], ]: |3 I( a! j .8 d& {* H$ y2 L- T i
qm-1*rm≡qm (mod n)8 S+ R" @1 J" z$ C' z
上述等式相乘,得:6 G" \1 t1 m! U1 q
a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>- }+ s( k3 n& F. D
a*(q1*q2*...*qm)≡rm (mod n)
8 t2 _: S8 X6 S; h' w6 Q; ] 如果对qi(1≤i≤m)进行如下的限定:
: B7 ^+ }8 v2 x/ z# c. K0 ^ a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
' |3 K: `9 g" L& D 则 qm=±14 M% l( M6 r: c7 i' F% F9 B- ^0 G
即 a与q1*q2*...*qm互逆5 _6 a7 j E d# I# s, h+ G
例 求28在299的逆! Q- V; R9 \* p! S: s
28*11≡9 (mod 299)
5 G+ P) |+ s$ q& }5 z- h: P1 @ 9*33≡-2 (mod 299)& y/ V- ?8 i. ]" ?
-2*-150≡1 (mod 299)& P# D ^) U/ s5 B2 x
逆为: 11*33*-150≡-32 (mod 299)2 U8 t( q. I1 q; E3 D
28*-22≡-1 (mod 299)
- Y K% c) D! Y1 I& a$ {8 E 但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。 ?' @% M; }" r2 R* D1 [2 O4 ?
下面给出其中一个算法:
* J9 k. h( x8 c; @$ N, v! E( i9 y 1 输入a,n ; t# Y8 B; z! V) L; B1 B& |8 q
2 resulte = 1 ; 保存逆的结果
( O$ c6 E0 |& b# _+ G, i. b g/ e/ U 3 r=n/a+1 ; 保证 r*a>n
0 f+ t. R0 Q5 t) L6 h0 @ 4 q=r*a-n ; 得到余数,该余数小于a
+ X7 F: v3 H& ]4 T: n0 _( I 5 resulte=(resulte*r)%n " g/ S# a, P+ E; B: i
6 if q=1 then print(逆为: resulte) return resulte
2 ~! x4 [* j: H; i) S3 |8 j0 g0 t 7 if q=0 or q=a then print(存在因子: a) return a ;/ d% H6 K1 _8 f$ Y2 q* f
8 a=q. ?: q, g: d; P( K/ n
9 goto 3
; X. S4 t' Y2 {& l1 y4 {+ a# }& |( Y6 N7 t" P( @" r+ C9 i& ~
|
zan
|