在Python 3模幂的实现 [英] Modular exponentiation implementation in Python 3

问题描述

基本上，这是一个家庭作业的问题。我应该落实Python3这两个伪code算法。我做错了什么，我想不出什么（好像这应该是简单的，所以我不知道/我的拙劣这一点。这可能是我的算法或者我缺乏与Python的经验。我'不敢肯定它）。

Basically this is a homework question. I'm supposed to implement these two pseudo-code algorithms in Python3. I'm doing something wrong and I can't figure out what (it seems like this should be simple so I'm not sure what/where I botched this. It could be my algorithm or my lack of experience with Python. I'm not sure which.).

请告诉我，我做错了什么，不要发布任何code。如果我得到code的答案我会挂剽窃（这一点我非常不希望）。

Please tell me what I did wrong, don't post any code. If I get code for an answer I'll get pegged for plagiarism (which I very much do not want).

第一种算法（基本扩展）：

The first algorithm (base expansion):

    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}

第二算法（模块化扩展）：

the second algorithm (modular expansion):

    procedure modular exponentiation(b: integer, n = (ak-1ak-2...a1a0)2, m: positive integers)
    x := 1
    power := b mod m
    for i := 0 to k - 1
        if ai = 1 then x := (x * power) mod m
        power := (power * power) mod m
    return x {x equals bn mod m}

看起来很简单，无论如何，这是我在Python3实现（我求求所有Python程序员宽恕在那里，这对我来说是一个非常新的语言）

Seems simple enough anyway, here's what I implemented in Python3 (and I beg forgiveness of all Python programmers out there, this is a very new language for me)

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 ⁶⁴⁴ 模645，我得到了答案79，但正确的答案应该是436。

This seems like it should work, but when I attempt to solve 7⁶⁴⁴ mod 645 I get the answer 79 but the right answer should be 436.

如果任何人都可以指出我的错误，而无需实际给我任何code，我会非常AP preciative。

If anyone could point out my mistakes without actually giving me any code I'd be extremely appreciative.

推荐答案

您的方法只会工作。如果B等于2，这是一样的幂的平方，但它会用b情况下未能> 2，具体方法如下：

Your method will only work if b equals 2, which is same as exponentiation by squaring but it will fail in cases with b > 2. Here's how:

您字符串n可以包含数字的范围在[0，B-1]，因为它是数n在基地B中的重presentation。在您的code，你只检查数字1，而在B = 7的情况下，可以在区间[0,6]的任何数字。你必须修改你的算法如下：

Your string n can contain numbers in the range [0,b-1] as it is the representation of number n in base b. In your code, you only check for digit 1, and in the case of b = 7, there can be any digit in the range [0,6]. You have to modify your algorithm as follows :

// 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

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

You should now get the correct answer.

这篇关于在Python 3模幂的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！