python - python3中计算特定mod的函数

Question

m, y, n, r我有四个像这样的大数字（最多 100 位）m * y mod n = r。我知道 and 的价值m,n，r我想找到 的价值y。有这样做的功能python3吗？（如 中的powmod函数gmpy2）

Answer 1

如果r您的问题中的值保证为1，则有一些可用的 Python 函数，例如invertgmpy 或gmpy2模块中的函数。我还没有找到您想要的更通用的除法功能。您可以使用标准的反转函数，但它们将不允许一些实际可以完成的除法。

这是我刚刚编写的一个函数，它基于Wikipedia 中的示例代码，尽可能高效。使用您的术语，调用divideresidues(r, m, n).

def divideresidues(dividend, divisor, modulus):
    """Return the dividend / divisor modulo modulus"""
    r, newr = modulus, divisor
    t, newt = 0, 1
    while newr != 0:
        quotient, remainder = divmod(r, newr)
        r, newr = newr, remainder
        t, newt = newt, t - quotient * newt
    if t < 0:
        t = t + modulus
    quotient, remainder = divmod(dividend, r)
    if remainder:
        raise ValueError('Bad division in divideresidues()')
    return t * quotient % modulus

divisor这与欧几里得算法具有相同的效率，即和中较小的位数的五倍modulus。的大小dividend基本上是无关紧要的。在您的情况下，这意味着最多 500 步。这听起来像是一个很大的数字，但我用更大的数字对其进行了测试，它似乎足够快，而且这 500 步很少发生——基本上是斐波那契数列中的连续数字divisor。modulus