在Python模反元素功能 [英] Modular multiplicative inverse function in Python
问题描述
有没有一些标准的Python模块包含一个函数来计算一个数值模反元素,即一批 Y = invmod(X,P)
,使得 X * Y == 1(模p)
?谷歌似乎并没有给这个有什么好的提示。
Does some standard Python module contain a function to compute modular multiplicative inverse of a number, i.e. a number y = invmod(x, p)
such that x*y == 1 (mod p)
? Google doesn't seem to give any good hints on this.
当然,人们可以拿出自酿10内胆扩展欧几里德算法,但为什么重塑轮。
Of course, one can come up with home-brewed 10-liner of extended Euclidean algorithm, but why reinvent the wheel.
例如,Java的的BigInteger
的 modInverse
方法。不Python中有相似的地方?
For example, Java's BigInteger
has modInverse
method. Doesn't Python have something similar?
推荐答案
也许有人会觉得有帮助(从<一个href="https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm">wikibooks):
Maybe someone will find this useful (from wikibooks):
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
这篇关于在Python模反元素功能的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!