- 在线时间
- 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
 |
以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。
: R+ t5 d! R& T: ^/ O8 z8 O设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m
0 g" j6 |% j+ ~' m/ N. s7 A a*r1≡q1 (mod n)
; Z7 B& R5 v8 y6 X+ S& k q1*r2≡q2 (mod n)& A# K, Y# Q5 B/ [9 m
q2*r3≡q3 (mod n)8 b+ U% n. X. e# M' T, V% k
.
( h; A% D& |- L0 d* j3 O5 Y .& g7 g( i# f" l! j0 E- j
.
- v" }& q* }! Y9 X% v: d0 o qm-1*rm≡qm (mod n)
: p/ C5 G# b0 l: n 上述等式相乘,得:; l O! e! k0 n/ `
a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
- E* a* ?& B2 L# E4 a* P: B/ m+ e a*(q1*q2*...*qm)≡rm (mod n)
/ \' v( w1 x$ x 如果对qi(1≤i≤m)进行如下的限定:
$ q$ d2 s% E' @% u5 ~5 U a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|3 \0 C& ]! b" d& C8 E* |% Y1 d. T1 E$ ?
则 qm=±1
( U$ l: a, ^( @; N& B# _1 w 即 a与q1*q2*...*qm互逆. ]2 s+ u2 @5 P' k) S$ R
例 求28在299的逆) ^# X% o* j: d, x" r
28*11≡9 (mod 299)
' u3 P" w) [1 E* S 9*33≡-2 (mod 299)
2 ~1 W0 e" A% n+ n -2*-150≡1 (mod 299)" Y1 m2 P2 k8 h0 }2 a
逆为: 11*33*-150≡-32 (mod 299)& T1 w5 N$ i7 O, d: F6 F4 l' T
28*-22≡-1 (mod 299)2 C& L* N$ s8 ]: z$ ]
但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。
0 S7 h3 ^0 o7 v& Y8 | 下面给出其中一个算法:
/ h, D# R: T; L; U7 L# B 1 输入a,n
: _' Q/ k3 ? B/ g: T 2 resulte = 1 ; 保存逆的结果 & @1 I! }' K# \
3 r=n/a+1 ; 保证 r*a>n& p! M1 K+ l1 t1 M: ~& c4 D$ u
4 q=r*a-n ; 得到余数,该余数小于a
8 u2 l6 j5 F1 }4 r; d* d7 x 5 resulte=(resulte*r)%n 3 r0 h1 N: @5 M( O, f
6 if q=1 then print(逆为: resulte) return resulte. v$ ]" ?* Z( Q: V
7 if q=0 or q=a then print(存在因子: a) return a ;" x& G* Z- {% G" {% p1 _' K
8 a=q9 j" {7 W) |% o1 }% ]5 I, H% M
9 goto 3
0 W3 i! @) h6 ?0 h- G4 g
& M; a& C( \0 d, \ |
zan
|