python - 为什么 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

您的函数 non_recursive_expmod 中有一些可疑步骤:删除 x 和 y 的 %m 在开始。两者都不需要。

此外，使用 y = y//2 确保 y 的除法是整数除法。

整个函数应该是这样的:

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