Модуль силы больших чисел

Question

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

pow(45, x) mod 257

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

Как я могу выполнить этот расчет?

Answer 1

некоторый псевдокод

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)    

Answer 2

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

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

1. Первое вычисление 45 ^ 2, 45 ^ 4, 45 ^ 8 мод 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-разрядном целочисленном типе.

Answer 3

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

Answer 4

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

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

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

A^4 = (A^2)^2

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