Модульная мощность больших чисел

Я пытаюсь реализовать алгоритм SAFER +. Алгоритм требует найти модуль степенной функции следующим образом:

pow(45, x) mod 257

Переменная x является байтовой и, следовательно, может находиться в диапазоне от 0 до 255. Соответственно, результат функции мощности может быть ОЧЕНЬ большим, что приведет к неправильным значениям, если она реализована с использованием 32- или 64-битных целых чисел.

Как я могу произвести этот расчет?


algorithm math language-agnostic modulus
person Eng. Aws    schedule 27.11.2011    source источник
comment
@esskar: Если я не совсем ошибаюсь и правильно помню, что существуют специальные формулы для вычислений в пространствах модулей, исчисление модулей является важной частью вопроса, поэтому вопрос не зависит от языка.   -  person thiton    schedule 27.11.2011
comment
Вводное чтение: Мультипликативная группа целых чисел. Я слишком давно не могу ответить, но, может быть, кто-то вспомнит.   -  person thiton    schedule 27.11.2011
comment
Существует реализация SAFER +, написанная на C, которую вы можете изучить здесь: schneier.com/book-applied -source.html   -  person Robert Harvey    schedule 27.11.2011

Ответы (4)


arrow_upward
21
arrow_downward

какой-то псевдокод

function powermod(base, exponent, modulus) {
    if (base < 1 || exponent < 0 || modulus < 1)
        return -1

    result = 1;
    while (exponent > 0) {
       if ((exponent % 2) == 1) {
           result = (result * base) % modulus;
       }
       base = (base * base) % modulus;
       exponent = floor(exponent / 2);
    }
    return result;
}

и позвони

powermod(45, x, 257)
person esskar    schedule 27.11.2011

arrow_upward
13
arrow_downward

Выполните возведение в степень, повторяя возведение в квадрат, уменьшая по модулю после каждой операции. Это очень стандартная техника.

Рабочий пример: 45^13 mod 257:

  1. Сначала вычислите 45 ^ 2, 45 ^ 4, 45 ^ 8 mod 257:

    45 ^ 2 по модулю 257 = 2025 по модулю 257 = 226

    45 ^ 4 по модулю 257 = 226 ^ 2 по модулю 257 = 51076 по модулю 257 = 190

    45 ^ 8 по модулю 257 = 190 ^ 2 по модулю 257 = 36100 по модулю 257 = 120

  2. Затем используйте двоичное расширение 13, чтобы объединить их и получить результат:

    45 ^ 13 по модулю 257 = 45 ^ 1 * 45 ^ 4 * 45 ^ 8 по модулю 257

    45 ^ 13 по модулю 257 = 45 * 190 * 120 по модулю 257

    45 ^ 13 по модулю 257 = 8550 * 120 по модулю 257

    45 ^ 13 по модулю 257 = 69 * 120 по модулю 257

    45 ^ 13 по модулю 257 = 8280 по модулю 257

    45 ^ 13 по модулю 257 = 56

Обратите внимание, что промежуточные результаты вычислений никогда не превышают 257 * 257, поэтому это можно легко выполнить в 32-битном целочисленном типе.

person Stephen Canon    schedule 27.11.2011

arrow_upward
5
arrow_downward

Основной подход состоит в возведении в квадрат или умножении в зависимости от разряда экспоненты и выполнении модульного сокращения на каждом шаге. Алгоритм называется (двоичное) модульное возведение в степень.

person Brett Hale    schedule 27.11.2011

arrow_upward
3
arrow_downward

Рассмотрим простую идентичность:

mod(A^2,p) = mod(A,p)*mod(A,p)

Также обратите внимание, что

A^4 = (A^2)^2

Другие степени легко вычисляются, если вы знаете двоичное представление конечной экспоненты, которую хотите вычислить.

person Community    schedule 27.11.2011