python3中的模幂实现

Question

基本上这是一个家庭作业问题。我应该在Python3中实现这两个伪代码算法。我做错了什么，我不知道是什么（这看起来应该很简单，所以我不知道我在哪里搞错了）。可能是我的算法，也可能是我对Python缺乏经验。我不确定是哪个。）。在

请告诉我我做错了什么，不要发布任何代码。如果我得到了一个答案的代码，我会因为剽窃而受到惩罚（这是我非常不想要的）。在

第一个算法（基扩展）：

    procedure base expansion(n, b: positive integers with b > 1)
    q := n
    k := 0
    while q ≠ 0
        ak := q mod b
        q := q div b
        k := k + 1
    return (ak-1, ... , a1, a0) {(ak-1 ... a1 a0)b is the base b expansion of n}

第二种算法（模展开）：

^{pr2}$

看起来很简单，下面是我用Python3实现的（我请求所有Python程序员原谅，这对我来说是一种非常新的语言）

def baseExp(n, b):
    q = n
    a = []
    while (q != 0):
        a.append(q % b)
        q = q // b
        pass
    return a

def modularExp(b, n, m):
    a = baseExp(n, b)
    x = 1
    power = b % m
    for i in range(0, len(a)):
        if (a[i] == 1):
            x = (x * power) % m
            pass
        power = (power * power) % m
        pass
    return x

这似乎应该行得通，但当我试图解7⁶⁴⁴mod 645时，我得到了79的答案，但正确的答案应该是436。在

如果有人能指出我的错误而不给我任何代码，我将不胜感激。在

Answer 1

您的方法只有在b等于2时才有效，这与平方求幂相同，但在b>；2的情况下它将失败。方法如下：

字符串n可以包含范围为[0，b-1]的数字，因为它是以b为底的数字n的表示形式。在代码中，只检查数字1，在b=7的情况下，范围[0,6]中可以有任何数字。您必须按如下方式修改算法：

// take appropriate remainders where required
// Correction 1 :
In the for loop,
Check if a[i] = 1, then x = x * power
else if a[i] = 2, then x = x * power^2
else if a[i] = 3, then x = x * power^3
.
.
.
.
till a[i] = b-1, then x = x * power^(b-1)
// Correction 2 :
After checking a[i] 
power = power^b and not power = power^2 which is only good for b = 2

你现在应该得到正确的答案了。在