用於計算python3中特定mod的函數

我有四個大數字（最多100位數），如m, y, n, r那m * y mod n = r。我知道m,n和r的價值，我想找到y的價值。 python3有沒有這個功能？（如在gmpy2的powmod功能）用於計算python3中特定mod的函數

來源

2016-11-22 Richard

難道你不能只使用屬性'（m * y）mod n =（m mod n）*（y mod n）mod n'？ – Rojan

你問的只是'powmod'。您正在要求模塊化算術分割，通常使用[擴展歐幾里德算法]（https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm）。這很容易實現，但要小心檢查錯誤情況。 –

我知道，我只是說一個例子，我需要這樣的功能@RoryDaulton – Richard

如果r在您的問題的值被保證是1，還有一些可用的Python函數，如在gmpy或gmpy2模塊invert功能。我還沒有找到你想要的更一般的分工功能。你可以使用標準的反轉函數，但他們將不允許一些可以實際完成的分割。

下面是我剛纔寫的一個函數，它基於sample code in 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是斐波那契序列中的連續數字。

來源

2016-11-24 01:14:30

用於計算python3中特定mod的函數

回答

相關問題