- 在线时间
- 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
 |
以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。+ E& ]9 C3 _/ K
设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m9 m2 W, n' E" |3 ^% A8 [7 z
a*r1≡q1 (mod n)6 [. g, ]" x ]3 D3 m3 B
q1*r2≡q2 (mod n)# F4 [4 ]: B- n) n N% Y
q2*r3≡q3 (mod n), v2 A2 N+ P1 g6 L/ W% k
.
* i: ~; `& M0 m4 c6 x2 C j .; L; C1 ]; i- `+ e$ r! W$ [
.
- n5 y; v2 H# S6 m& H I qm-1*rm≡qm (mod n)
1 ]# f' }; b( W$ h1 T n$ q 上述等式相乘,得:+ T- R) u9 r; c
a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
/ Y# i$ D$ `) `( J a*(q1*q2*...*qm)≡rm (mod n) + e$ \0 e; a6 [9 G' {( l( h
如果对qi(1≤i≤m)进行如下的限定:
1 C$ u5 c9 j: Z0 k8 M' H a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
1 u' E t* h6 l7 z6 c 则 qm=±1
. ?1 [5 o: `& ]) S6 q7 [ 即 a与q1*q2*...*qm互逆
( s7 Y8 J5 ^3 U" z/ ?" l 例 求28在299的逆, V1 Y1 h$ }/ ?: U& @
28*11≡9 (mod 299)
; G9 c: ?' l. T. a& X 9*33≡-2 (mod 299)
2 S% H6 X: A( a. { -2*-150≡1 (mod 299), e0 h( A3 B; Q: U- {/ F& D5 `
逆为: 11*33*-150≡-32 (mod 299)
6 r2 Q3 R; ~8 M 28*-22≡-1 (mod 299)
3 v- ^, X# w6 h2 X) a 但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。+ Y3 `/ B& F8 n( {8 v
下面给出其中一个算法:
5 Z- e8 _7 `( U5 [2 w: [ 1 输入a,n ! M6 @" S; W6 g1 u; I
2 resulte = 1 ; 保存逆的结果
& p' h& r. {' @8 r% G 3 r=n/a+1 ; 保证 r*a>n
1 p) U+ R4 Q; p- j# H 4 q=r*a-n ; 得到余数,该余数小于a4 x1 y+ F* v7 E! C
5 resulte=(resulte*r)%n
9 w% H: g: C9 k 6 if q=1 then print(逆为: resulte) return resulte
- s4 t. f) x6 a, |0 J2 U 7 if q=0 or q=a then print(存在因子: a) return a ;( O, l9 N& t. b( b! r1 a
8 a=q
; O4 v7 w" V) d3 E( _ 9 goto 3: k8 {( P4 J& @, M/ E ]% `# S* S4 X
2 A, Q+ ~2 S* r
|
zan
|