爲什麼expmod的這兩個實現對於大值有所不同？

我寫了幾個函數做expmod，即(x ** y) % n。這些都是標準功能，我已經檢查並重新檢查了兩者，但找不到任何愚蠢的錯誤。爲什麼expmod的這兩個實現對於大值有所不同？

這裏的遞歸一個：

def expmod(x,y,m): 
    if y == 0: return 1 
    if y % 2 == 0: 
     return square(expmod(x,y/2,m)) % m # def square(x): return x*x 
    else: 
     return (x * expmod(x,y-1,m)) % m

...和這裏的非遞歸之一：

def non_recursive_expmod(x,y,m): 
    x = x % m 
    y = y % m 
    result = 1 
    while y > 0: 
     if(y%2 == 1): 
      result = (result * x) % m 
     x = (x*x) % m 
     y = y/2 
    return result

他們同意爲小值：

>>> expmod(123,456,789) - non_recursive_expmod(123,456,789) 
0

...但不適用於較大的：

>>> expmod(24354321,5735275,654) - non_recursive_expmod(24354321,5735275,654) 
-396L

發生了什麼事？

來源

2011-12-20 fredley

有POW（）函數在python中。第三個參數可以是mod。 – 2011-12-20 15:10:03

'TypeError：pow expected 2 arguments，got 3' – fredley 2011-12-20 15:16:01

@TomMedley：你可能做了一個從數學（來自數學導入*）的星形導入，它用數學庫的pow替換了內建的3個參數的pow，它只有2個 – DSM 2011-12-20 15:18:39

您的功能non_recursive_expmod有一些可疑的步驟：在開始時刪除%m爲x和y。兩者都不需要。

此外請確保y的劃分是使用y = y // 2的整數除法。

總體功能應該是這樣的：

def non_recursive_expmod(x, y, m): 
    result = 1 
    while y > 0: 
     if y % 2 == 1: 
      result = (result * x) % m 
     x = (x * x) % m 
     y = y // 2 
    return result

來源

2011-12-20 15:13:27 Howard

進行這些更改會完全破壞它！這個算法是正確的，如果你用小的值處理它，很清楚它正在做正確的事情。 – fredley 2011-12-20 15:17:44

啊，還有一個棘手的問題：使用'y = int（y/2）'。 – Howard 2011-12-20 15:21:03

已修復它，謝謝！將它添加到您的答案，以便我可以接受。 – fredley 2011-12-20 15:24:29

非遞歸不減少的Y情況下，它是奇數，甚至部分人需要的情況下，y == 1

來源

2011-12-20 15:19:48

我不確定你在說什麼。 – fredley 2011-12-20 15:22:33

一旦y == 1它的工作原理錯誤 – 2011-12-20 15:26:20

爲什麼expmod的這兩個實現對於大值有所不同？

回答

相關問題