Возведение в степень по модулю

Алгоритмизация / Возведение в степень по модулю

 

Во многих задачах, в частности, в криптосистеме часто приходится вычислять

xy % N

для x, y и N, состоящих из нескольких сотен битов. Как это сделать быстро?Результатом такого вычисления является остаток по модулю N, то есть число длиной несколько единиц — десятков битов.
Однако само xy может иметь гораздо большую длину.
Если в двоичной записи xy больше 32 битов, его уже невозможно представить в разрядной сетке типа int.
Поэтому применение алгоритма, выполняющего сначала возведение в степень, а затем деления с вычислением остатка, сильно ограничено разрядной сеткой и требуемым объемом вычислений.
Значение xy % N можно вычислить, начав с 1 и y раз умножив на x (каждый раз по модулю N). При этом все промежуточные результаты

x % N → x2 % N → x3 % N → … → xy % N

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

Однако можно воспользоваться свойством возведения в квадрат, реализующим идею:
Вычисление остатка от деления x в степени y на N
Таким образом, чтобы вычислить xy % N, нужно перемножить те степени x, которые соответствуют ненулевым позициям в двоичной записи y:

x25 = x16 · x8 · x1

Реализация на C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int modexp(int x, int y, int N)
{
  if (y == 0) return 1;
  int z = modexp(x, y / 2, N);
  if (y % 2 == 0)
    return (z*z) % N;
  else
    return (x*z*z) % N;
}
int main()
{
  int x, y, N;
  cout << "x= "; cin >> x;
  cout << "y= "; cin >> y;
  cout << "N= "; cin >> N;
  cout << modexp(x, y, N);
  cin.get(); cin.get();
  return 0;
}

Результат выполнения
Остаток от деления


Назад: Алгоритмизация

Комментариев к записи: 12

  • Возвести в степень по модулю довольно легко, даже при больших входных значениях. А вот вычисление дискретного логарифма , то есть нахождение показателя степени

  • Наталья
    Цитата: "При этом все промежуточные результаты x % N → x^2 % N → x^3 % N → … → x^y % N не превосходят N, и каждое умножение будет сравнительно быстрым." Если подходить к подобному методу с математической точностью, :) (а как же иначе), то он работает ТОЛЬКО в двух случаях: Первый - если х < N и х^y < N. В этом случае все степени по модулю будут дробные числа (меньше 1). И здесь, действительно, каждый последующий элемент цепочки x % N → x^2 % N → x^3 % N → … → x^y % N будет результатом умножения предыдущего на х. Второй - если х > N и х^y > N. В этом случае все степени по модулю будут целыми и каждый последующий элемент вышеуказанной цепочки будет результатом умножения предыдущего на х. А вот если х < N и х^y > N, то первый элемент цепочки всегда меньше 1, а последний x^y % N всегда больше 1. А это значит, что на каком-то этапе в этой цепочке появляется ПЕРВОЕ целое число, и дальше идут только целые. Так вот, ПЕРВОЕ целое НЕЛЬЗЯ (!!!) получить из последнего дробного путем умножения его на х. Это следовало бы оговорить. Пример. Пусть x = 3, y = 5, N = 20. x % N = 3 % 20 = 3/20 (целой части нет, поэтому остатком является р-т деления) x^2 % N = 9 % 20 = 9/20 (аналогично предыдущему) x^3 % N = 27%20 = 7 (первое целое) x^4 % N = 81%20 = 1 x^5 % N = 243%20 = 3 Итак, для первый двух (дробных) элементов цепи (3/20 и 9/20) и остальных, начиная с ЧЕТВЕРТОГО (1 и 3), выполняется правило - каждый последующий это результат умножения предыдущего на х = 3. Но это правило НЕ работает для ТРЕТЬЕГО элемента, поскольку он сам целый, а предыдущий дробный.

    • Елена Вставская
      Пока я не поняла, в чем проблема. Мы же анализируем только остаток от деления, а не произведение. По приведенному Вами примеру: 1. 3%20 = 3 2. 3*3%20 = 9%20 = 9 3. 9*3%20 = 27%20 = 7 4. 7*3%20 = 21%20 = 1 5. 1*3%20 = 3%20 = 3 Где мы не можем получить третий элемент?

      • Наталья
        Моя реплика, на которую Вы ответили, содержала ошибку. Прошу прощения. Тем не менее, привожу Вашу цитату: "Мы же анализируем только остаток от деления, а не произведение". Нет, мы анализируем возведение в степень по модулю (Алгоритмизация / Возведение в степень по модулю). В статье не сказано что анализируемое выражение x^у % N на самом деле является возведение числа х в степень у по модулю N. Поскольку возведение в степень можно представить в виде произведения, в статье совершенно справедливо используется поэтапный подход, при котором вначале находится x mod N = x % N, потом на его основе x^2 mod N = x^2 % N и так далее, до x^у mod N = x^у % N. Каждый следующий элемент этой цепочки, начиная со второго, вычисляется как произведение предыдущего на х по модулю N. Поэтому, отвечая на Ваш вопрос, говорю что вначале мы находим произведение (в чистом виде), а потом уже вычисляем величину этого произведения по модулю N, т.е. остаток от деления этого произведения на N.

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

  • Наталья
    Прошу прощения, мой предыдущий комментарий был некорректен - если делимое < делителя, то неполное частное 0, а остаток равен делимому.
    Но у меня есть еще замечания.
    1) Вначале небольшое дополнение. Если воспользоваться формулой (a·b) mod m = ((a mod m)·(b mod m)) mod m то при вычислении x^y % N каждый последующий элемент цепочки
    x % N → x^2 % N → x^3 % N → … → x^y % N
    начиная со второго, находится как произведение (по модулю N) предыдущего и первого элемента x^1 % N = x % N. Умножать на первый элемент порой удобнее, чем на x.
    2) В заключительной части, где предлагается подход с возведением в квадрат, объяснения практически нет. Там не делается акцента на главном - уменьшении количества итераций наполовину для четного у и наполовину +1 для нечетного у.
    В данном подходе базовым является случай с четным y = 2*k, когда цепочка вычислений имеет вид:
    (x^1)^2 % N → (x^2)^2 % N → (x^3)^2 % N → … → (x^k)^2 % N
    Каждый ее последующий элемент это результат умножения (по модулю N) предыдущего на x^2 или, с учетом п.1, это результат умножения (по модулю N) предыдущего на первый элемент (x^1)^2 % N
    В случае с нечетным y (y = 2*k + 1) в конец цепочки добавляется еще одна итерация. Этот элемент - результат умножения (по модулю N) k-го элемента ((x^k)^2 % N) на число х, и имеет вид x*(x^k)^2 % N
    3) Последний фрагмент лишен всякого смысла:
    "Таким образом, чтобы вычислить x^y%N, нужно перемножить те степени x, которые соответствуют ненулевым позициям в двоичной записи y: x^25 = x^16 · x^8 · x^0"
    Во-первых, выражение x^25 = x^16 · x^8 · x^0 неверно.
    Во-вторых, оборот "Таким образом" подразумевает, что идущие за ним выкладки вытекают из вышеприведенного, но это совсем не так. Автор затрагивает тему разложения показателя степени по степеням двойки, но никак ее не раскрывает. (Мне кажется, что он сам ее не понимает).
    Итак, одним из способов вычисления степени по модулю, а именно x^y mod N, является замена возведения в степень произведением. Для этого показатель степени у представляется в виде суммы степеней двойки, которые соответствуют ненулевым позициям в двоичной записи y. Продолжим на конкретном примере.
    Пусть у = 25, что в двоичной записи соответствует 11001. Ненулевые значения находятся в 0-й, 3-й и 4-й позициях. Значит, у = 25 = 2^0 + 2^3 + 2^4 = 1 + 8 + 16.
    Отсюда x^y = x^(1 + 8 + 16) = x * x^8 * x^16.
    Поэтому x^y mod N = (x * x^8 * x^16) mod N = ((x mod N) * (x^8 mod N) * (x^16 mod N)) mod N
    Дальнейшие вычисления не составляют никакой трудности

    • Елена Вставская
      "Во-первых, выражение x^25 = x^16 · x^8 · x^0 неверно." ...
      "Пусть у = 25... Отсюда x^y = x^(1 + 8 + 16) = x * x^8 * x^16."
      Комментарий сам себе противоречит. Очень трудно понять, с чем Вы не согласны.

  • Наталья
    Елена, прошу прощения, но я "мечу бисер перед ... ". Вы ничегошеньки не понимаете. Вам "трудно понять" самые простые вещи. Смысла заходить на эту страничку больше нет. Удачи Вам!

    • Пишу этот комментарий для всех тех, кто, как и я, попал сюда из поисковика и погряз в сомнениях, прочитав описание алгоритма от автора. Спасибо, Наталья! Алгоритм простой, результат дает правильный. Запараноил: "а вдруг?". Почитал приведенное автором описание алгоритма и... подумал "Неужели меня в школе неправильно учили?" Признаться честно, текст читал выборочно, т.к. интересовался исключительно алгоритмом. Но последние комментарии вроде бы всё расставили по своим местам. Итак... Елена, по поводу: __________________ "Во-первых, выражение x^25 = x^16 · x^8 · x^0 неверно." ... "Пусть у = 25... Отсюда x^y = x^(1 + 8 + 16) = x * x^8 * x^16." Комментарий сам себе противоречит. Очень трудно понять, с чем Вы не согласны. _________________ Любое число в нулевой степени = 1. Школьная формула. https://www.google.com/search?q=Любое+число+в+нулевой+степени При умножении степеней с одинаковым основанием их показатели складываются. Таким образом, x^16 · x^8 · x^0 = x^(16+8+0) = x^24... но никак не х^25. Не сейте сомнения в умах посетителей.

      • Елена Вставская
        Ну, спасибо, что хоть таким образом указали на опечатку. Исправила. Хотя бы без бисера)


Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *