为什么这两种expmod实现对于大值的结果不同？

Question

我写了几个函数来计算 expmod，也就是 (x ** y) % n。这两个函数都是标准的，我检查了很多遍，也没有发现什么低级错误。

这是递归版本的：

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

这是怎么回事呢？

Answer 1

非递归的情况下，如果y是奇数，它的值不会减少。而对于偶数的部分，当y等于1时，需要加一个else条件。

Answer 2

你的函数 non_recursive_expmod 有一些可疑的步骤：在一开始去掉 x 和 y 的 %m，这两个是没必要的。

另外，要确保对 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