- 在线时间
- 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
 |
以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。
" Q" z1 l: p. P设 (a,n)=1 (ri,n)=1 (qi,n)=1 1≤i≤m0 W2 K/ a9 P2 i J+ s" ^% P) u
a*r1≡q1 (mod n)
" ]. @& p( L7 L# h q1*r2≡q2 (mod n)
& z, Z$ w$ u6 I; D q2*r3≡q3 (mod n)! O K/ ]! t4 [8 Z0 O1 x
.
* n% l3 c' e% j$ r+ x .1 n9 k. G# ^2 L% n8 A
.
$ y, f ]! n! L' Z ` qm-1*rm≡qm (mod n)5 f' k2 @. M' b7 ?7 h
上述等式相乘,得:2 R3 Z- S# d. z& k! ^! `; X1 d; Q
a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
- t. y/ `5 N# ~# r a*(q1*q2*...*qm)≡rm (mod n)
5 Z; `# O; L& Y0 b 如果对qi(1≤i≤m)进行如下的限定:
: L: T5 t+ i' q% |" W0 b6 X6 r4 T a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|( B/ O; O! I( _7 {& Y8 q6 Q- ?
则 qm=±1+ I$ {( Q$ h. m
即 a与q1*q2*...*qm互逆. q7 ~; Y, l5 t
例 求28在299的逆
) t; r; }. X0 g9 P' `) | 28*11≡9 (mod 299)
7 d* u) @9 b! U% _5 e# q) R. M 9*33≡-2 (mod 299)
7 R6 L2 w5 ]0 ?7 C- O' Z! O -2*-150≡1 (mod 299); `7 H2 ]/ ?2 ]# z4 q% I
逆为: 11*33*-150≡-32 (mod 299)" c6 e4 `. n8 s2 i; l9 H
28*-22≡-1 (mod 299)
% b* x3 O1 e- Z: B" B, U 但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。
: P6 R7 N, S) j* q: _- s 下面给出其中一个算法:
p+ z% c$ R7 W3 w, M/ s- C 1 输入a,n 1 {% m1 z5 I3 a* M# {% R& C
2 resulte = 1 ; 保存逆的结果
0 L& _5 ?. ~$ }3 o; X 3 r=n/a+1 ; 保证 r*a>n
c: l" _& u! K% f 4 q=r*a-n ; 得到余数,该余数小于a9 `& H/ f- ]& W
5 resulte=(resulte*r)%n
& R [3 O* }2 a, k+ n. @0 B0 T 6 if q=1 then print(逆为: resulte) return resulte
& Q* g" A9 G; j. b! K. ]) s( K) f 7 if q=0 or q=a then print(存在因子: a) return a ;: d3 F0 U6 L: M3 t I' L
8 a=q" q8 B9 O% Z' n+ m% B" G
9 goto 3& L4 V* C* w) S ^) K! V3 m4 M
# v# m, z5 R3 [' C6 L. W3 m3 R. |
|
zan
|