python - 求解模方程（Python）

Question

我有一个似乎很容易在 Python 中解决的问题，但由于我是 python 新手，所以我不知道如何解决这个问题。

我想要解决的只是...

(x * e) mod k = 1 （其中e和k是已知值）

有什么简单的方法可以做到这一点吗？

Answer 1

如果您更愿意使用流行的数学库gmpy而不是编写自己的算法，那么求解方程（即求模逆）的函数称为 invert()。安装当前版本的 gmpy（撰写本文时的版本 2）后，您只需执行以下操作：

>>> import gmpy2
>>> x = gmpy2.invert(e, k) # (Supply e and k here)

注意：gmpy 将以其本机 mpz（多精度整数）格式返回值，但是您可以像 Python 代码中的常规 int 一样处理该值，或者如果您愿意，可以将其显式转换为 int：

>>> x = int(gmpy2.invert(3, 7))

这是 gmpy2.invert() 的文档：

反转（x，m）-> mpz

返回 y 使得 x*y == 1 (mod m)。如果不存在逆，则引发 ZeroDivisionError。

这种方法的优点是 gmpy 算法速度很快，您不需要输入任何额外的代码。缺点是您必须导入第三方模块。

Answer 2

搜索x基本上是在寻找emod的逆元素，k这可以通过 扩展欧几里得算法完成，该算法很好地实现并用于模逆：

# Iterative Algorithm (xgcd)
def iterative_egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q,r = b//a,b%a; m,n = x-u*q,y-v*q # use x//y for floor "floor division"
        b,a, x,y, u,v = a,r, u,v, m,n
    return b, x, y

def modinv(a, m):
    g, x, y = iterative_egcd(a, m) 
    if g != 1:
        return None
    else:
        return x % m

_{注意：我不拥有代码}

和用法：

>>> e = 3
>>> k = 7
>>> x = modinv(e,k)
>>> x
5
>>> e*x % k
1

Answer 3

从Python 3.8开始，现在最简单的方法是：

pow(e, -1, k) # x is the output of this statement

例子：

>>> pow(38, -1, 97)
23
>>> 23 * 38 % 97 == 1
True