python - Python中的连续正方形

Question

我正在用 python 编写一个程序，该程序涉及将一个数字提高到一个极高的指数。为此，我正在尝试实施连续平方法以减少计算时间并消除溢出错误的风险。

连续的正方形是为了做同样的事情，base**exponent % modulo我写的当前函数是这样的：

def ssp(b, m, n):
    ssp = 1
    while n>0:
        if n % 2 == 1:
            ssp = b*ssp % m
        b = b**2 % m
        n = n // 2
    return ssp

当我用我测试函数时，ssp(7, 13, 93)我得到的答案是 8，应该是 19。有人可以提示我做错了什么吗？

Answer 1

你正在做pow(7, 93, 13)=>8但你想要的是pow(7, 13, 93)=>19

交换函数的第二个和第三个参数。

>>> def ssp(b, n, m):
...     ssp = 1
...     while n>0:
...         if n % 2 == 1:
...             ssp = b*ssp % m
...         b = b**2 % m
...         n = n // 2
...     return ssp
... 
>>> ssp(7, 13, 93)
19

Answer 2

我认为你只是把论点的顺序弄错了。第三个参数是指数；第二个是模数。这可能不是你想要的。