- 在线时间
- 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
 |
以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。
, K% |5 {! G7 ^2 n3 s5 \3 Z. R设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m9 V5 t) ~4 j. A+ z
a*r1≡q1 (mod n)7 W4 V* S r! Q5 z: a" e* z
q1*r2≡q2 (mod n)
: ^/ F+ @8 W% L# ]* `/ u; D q2*r3≡q3 (mod n)
, Y7 J; v, g2 m+ Y .
6 K* B$ z, r# ~4 I2 S+ E .
; }3 w8 `/ n% I3 `9 e9 _ .$ s, n% d {5 [
qm-1*rm≡qm (mod n)/ L, l( R7 |% t& @
上述等式相乘,得:1 C* ^- a( B& ]3 `
a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>2 U, d3 s8 `" S( t- ~) O; r
a*(q1*q2*...*qm)≡rm (mod n) , P2 m7 z5 w/ g0 R
如果对qi(1≤i≤m)进行如下的限定:/ ^7 {1 o2 |9 S3 j! _1 \* R
a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|* l2 C1 Q+ G7 W# m" p4 C% m
则 qm=±1
& \' S8 w* h) i 即 a与q1*q2*...*qm互逆
8 u0 _4 m: g& w( T, N1 r& P 例 求28在299的逆
& n! f$ |/ B1 u/ K" T' b 28*11≡9 (mod 299)+ X, l* {: j0 u
9*33≡-2 (mod 299)
% S( g7 D+ w2 y, c% _0 A -2*-150≡1 (mod 299)
; i% g0 F8 F) {% T/ b 逆为: 11*33*-150≡-32 (mod 299)
8 o# I5 k: z2 Q& f" u 28*-22≡-1 (mod 299)
3 }3 L: P4 T. u' V) [ 但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。$ c7 S. L# \2 g- \+ O' \* D
下面给出其中一个算法:5 h- G7 U- N. \6 A8 n) a. O
1 输入a,n
- I0 a& ^- n$ f4 I- ~ 2 resulte = 1 ; 保存逆的结果 / e( a1 X. G: p* |
3 r=n/a+1 ; 保证 r*a>n
; Y: O) f8 p4 r0 Q8 y 4 q=r*a-n ; 得到余数,该余数小于a0 W+ L% G9 O( Y3 ]& S( }/ Z7 t4 y
5 resulte=(resulte*r)%n
% j: g3 R( i/ h; K b 6 if q=1 then print(逆为: resulte) return resulte& k. u4 Y4 i; K9 z; S
7 if q=0 or q=a then print(存在因子: a) return a ;1 _! \. G% S, j; X( x
8 a=q2 i( X6 }: W! g
9 goto 3
) g% q1 r2 Y" S; Z4 w( v" O- P& o$ h0 F( |
|
zan
|