模逆元
定义
a的模逆元是满足
a
⋅
x
acdot x
a⋅x模一个模数
x
x
x:
a
⋅
x
≡
1
a cdot x equiv 1 text{ ~~~~mod m.}
x
x
x表示为
a
−
1
a^{-1}
a−1
m
=
4
,
a
=
2
m=4, a=2
m=4,a=2，通过检查m的所有余数，可以很清楚地知道不能找到满足上面等式的
a
−
1
a^{-1}
a−1。当且仅当m和a互质的时候，模逆是存在的。
下面是模拟存在时候找到它们的两种方法，还有一种方法是在线性时间内找到所有数的模逆。
扩展欧几里得算法（Extended Euclidean algorithm)
a
⋅
x
+
m
⋅
=
1
a⋅x+m⋅y=1
求模逆的代码
原文地址:https://blog.csdn.net/qq_42725437/article/details/134770869
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_36124.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
