求解模方程 (Python)

Question

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

我想要解决的只是......

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

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

Answer 1

搜索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