Python 中的模块化乘法反函数 [英] Modular multiplicative inverse function in Python
本文介绍了Python 中的模块化乘法反函数的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
某些标准 Python 模块是否包含计算一个数的模乘逆的函数,即一个数字 y = invmod(x, p)
使得 x*y == 1 (mod 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-liner 扩展欧几里得算法,但为什么要重新发明轮子.
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?
推荐答案
Python 3.8+
y = pow(x, -1, p)
Python 3.7 及更早版本
也许有人会发现这很有用(来自 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屋!
查看全文