- 在线时间
- 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
 |
以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。" h: v l7 S7 @. O7 _( n0 Z
设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m" P' b& g, F/ T: s# }: [# a
a*r1≡q1 (mod n)% h" i, X6 T; H l4 r. A
q1*r2≡q2 (mod n)* r, x+ u: |* K
q2*r3≡q3 (mod n)
, n1 c @- e5 L# P. ^ .
. q) Z0 H/ M3 u# H3 ?8 c- {. C .
. C( G# g% Y+ ]) Q .
6 P, `( e# k) X" _3 R, D qm-1*rm≡qm (mod n)
# q; f; B3 @3 W5 | 上述等式相乘,得:
. p7 M5 V5 B" C, z! `/ V a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>1 S8 W+ c# D& P5 m- A
a*(q1*q2*...*qm)≡rm (mod n) % a- S6 Z( M4 e; Q7 Q4 P& I
如果对qi(1≤i≤m)进行如下的限定:/ x2 W5 \9 w9 p: T) \
a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
2 [! U/ t0 K; {( c; l# g- v- m 则 qm=±1
& V; E! N7 W9 U, z' @) M& R. B 即 a与q1*q2*...*qm互逆
. m5 D6 y+ n }& `9 G: g7 M7 K 例 求28在299的逆
[- E) x9 U. R7 p, ?) M! q1 e 28*11≡9 (mod 299)/ Z0 A# u4 e ]% q* p" s
9*33≡-2 (mod 299)/ O- o9 ~9 Z( L! I- M2 H8 R/ E
-2*-150≡1 (mod 299)
% q+ p2 I9 j4 ^3 ?3 f 逆为: 11*33*-150≡-32 (mod 299)# k9 I" R3 `! Q$ |% \
28*-22≡-1 (mod 299)
- R; s3 t; z; Z' f 但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。# i# A- Z% i3 y
下面给出其中一个算法:% N1 M: V! U4 T- z5 R
1 输入a,n
! v" T6 q- a0 G% H* R/ V 2 resulte = 1 ; 保存逆的结果
/ ]: W( g" e/ M: I- ~( j0 u 3 r=n/a+1 ; 保证 r*a>n
5 L2 Y1 {0 X8 _. c V 4 q=r*a-n ; 得到余数,该余数小于a
- w3 _3 e! Y0 j1 o) i" n4 L; k6 I" o 5 resulte=(resulte*r)%n
! `! ^7 W& @1 B2 q3 y 6 if q=1 then print(逆为: resulte) return resulte
, a7 Y4 T0 K3 X6 R; a7 f1 E ? 7 if q=0 or q=a then print(存在因子: a) return a ;6 L, q) w+ u9 f8 F7 ~ J7 |
8 a=q
2 |( w0 W% A6 z3 N( c+ F% m! p0 v4 s# ? 9 goto 38 o) x; o2 @1 {3 j
6 d7 e, x6 v* Q) u( U5 H7 o# Q; E
|
zan
|