模量反算卡住

這裏是我到目前爲止的代碼：模量反算卡住

def mod_div(a, b, n): 

if gcd(b,n) != 1: 
    return 'Undefined'  

for x in range(1, n): 
     if b*x%n == a%n:  
      return x

這個代碼利用函數GCD（），我提出和返回GCD，然後我用它來計算逆。我搜索了這些問題，他們中沒有一個似乎給我正確的答案。

我的問題是：當我做div_mod（3,2,7）時，代碼返回5，因爲它應該。但是，當我爲大數目（例如n> 10000）執行此操作時，解決方案需要很長時間才能計算，因爲通過n進行迭代才能找到正確的數字。

我試着查看其他問題，並在他們的答案中，他們都有類似的事情，但不是去爲我在n，他們都返回x％n，如果gcd！= 1。這不會幫助我，並沒有給出正確的答案。

例如。如果我使用a = 12，b = 3和n = 11，它應該返回4，但我發現除我的所有功能都返回1.

我想知道是否有更有效的方式來使用eulids擴展定理除了測試每個n，並希望一個作品。

來源

2014-01-17 MD-4

你說得對，擴展歐幾里德算法解決了這個任務。然而，你不需要叫它n次 - 你只需要它一次。檢查http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

這裏是http://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm

def 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 
     b,a, x,y, u,v = a,r, u,v, m,n 
    return b, x, y 

def modinv(a, m): 
    g, x, y = egcd(a, m) 
    if g != 1: 
     return None # modular inverse does not exist 
    else: 
     return x % m

O（1）空間和周圍Ø勢在必行蟒蛇算法（log n）的最壞情況下的時間。

現在，分模n，我們定義

def moddiv(a, b, n): 
    binv = modinv(b, n) 
    if not binv: 
     return None 
    return a * binv % n

來源

2014-01-17 08:24:18

謝謝。然而，對於我的測試用例，a，b，c = 14,67,88應該輸出58，但在這種情況下，當我在modinv函數中放入a和m時，它將返回None而不是58.我有困難時間理解爲什麼。另外，我注意到你在你的答案中使用了一個modinv，我使用了b。我不明白爲什麼。 –

「a」的倒數就是這樣的元素b，即「a * inv = 1 mod m」，所以你只需要兩個參數。我想你正在尋找'a * inv = b'，但是它足以將結果乘以'b'並採用'mod m'。 –

Ps。感謝您接受答案。但是要知道，只要事情變得清晰，就接受了，沒有什麼不對;） –

模量反算卡住

回答

相關問題