解决模方程（Python）

Question

我在Python中遇到了一个看似简单的问题，但由于我是新手所以不知道如何解决。

我要解决的问题是...

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

有没有简单的方法来解决这个问题？

- Scalahansolo

---

(x*e) mod K = 1 或者 x * (e mod k) = 1？ - DhruvPathak

抱歉 (x*e) mod k = 1 - Scalahansolo

我猜你说的是模运算而不仅仅是简单的“%”函数，我的理解正确吗？ - Vyktor

Answer 1

搜索x基本上是在寻找模k下的e的逆元素，这可以通过扩展欧几里得算法来实现，该算法已经很好地实现并用于模反演。

# 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

- Vyktor

Answer 2

自 Python 3.8 以来，现在的简单方法是：

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

例子：

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

- Flair

Answer 3

如果你更喜欢使用流行的数学库 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()的文档：

invert(x, m) -> mpz

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

这种方法的优点是gmpy算法速度快，且不需要键入额外代码。缺点是需要导入第三方模块。

- Christian Abbott

---

x = int(sympy.invert(3, 7)) works too, for those who have problems getting gmpy2 (like me) but do have access to sympy - Linear Christmas