为什么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的这两个实现对于大值有所不同？

回答

相关问题