Модульная реализация возведения в степень в Python 3

По сути, это вопрос домашнего задания. Я должен реализовать эти два алгоритма псевдокода в 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}

второй алгоритм (модульное расширение):


    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, это очень новый язык для меня)

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

Кажется, это должно работать, но когда я пытаюсь решить 7644 mod 645, я получаю ответ 79, но правильный ответ должен быть 436.

Если бы кто-нибудь мог указать на мои ошибки, не давая мне никакого кода, я был бы очень признателен.


python-3.x python algorithm pseudocode modular-arithmetic
person Paul Nelson Baker    schedule 14.09.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Ваш метод будет работать только в том случае, если b равно 2, что аналогично возведению в степень путем возведения в квадрат, но он не работает в случаях, когда b > 2. Вот как:

Ваша строка n может содержать числа в диапазоне [0,b-1], так как это представление числа n в базе b. В вашем коде вы проверяете только цифру 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

Теперь вы должны получить правильный ответ.

person sanchit.h    schedule 14.09.2013
comment
Огромное спасибо. Я ломал голову всю неделю, и я был очень болен. Предложенные вами изменения заставляют алгоритм работать. Чего я не понимаю, так это того, почему псевдокод в моей книге не был написан так, как вы описали (я дважды проверил свою книгу, чтобы убедиться, что я не просто опечатался здесь, так что либо я не понимаю обозначение книги или оно было неправильным). Еще раз спасибо, вы были спасением! - person Paul Nelson Baker; 14.09.2013
comment
Кажется, что псевдокод для «модульного возведения в степень процедуры» в вашей книге был написан специально для b = 2, как указано в «n = (ak-1ak-2...a1a0)2», а он содержит индекс «b ' вместо 2 в "расширении базы процедур". - person sanchit.h; 14.09.2013
comment
О БОЖЕ МОЙ! У меня ушло пару часов, но я на самом деле понял, что должно произойти (по иронии судьбы именно ваш последний комментарий заставил меня понять это). Для строки a = baseExp(n, b), если мы изменим ее на a = baseExp(n, 2), она преобразуется в двоичный код, который является BASE 2 и работает для исходного псевдокода! Вот почему в книге написано так! Я должен Вдвойне поблагодарить вас, я бы не понял, если бы не ваша наблюдательность! - person Paul Nelson Baker; 15.09.2013