Русская Википедия:Алгоритмы быстрого возведения в степень по модулю
Алгоритмы быстрого возведения в степень по модулю — разновидность алгоритмов возведения в степень по модулю, широко использующихся в различных криптосистемах, для ускорения вычислительных операций с большими числами.
Метод с использованием Китайской теоремы об остатках
Описание метода
Шаблон:Mainref Пусть требуется вычислить <math>S=x^a\bmod n</math>, где числа <math>x,a,n</math> достаточно большие и пусть модуль может быть разложен на простые делители <math>n=p_1p_2...p_j</math>. Тогда для быстрого возведения в степень по модулю можно воспользоваться китайской теоремой об остатках и решить систему уравнений (предварительно посчитав вычеты <math>x^a\equiv r_i\pmod {p_i}</math> с использованием теоремы Ферма, где <math>i=1,2,...,j</math>):
<math>\begin{cases} x^a\equiv r_1\pmod {p_1},\qquad 0\leqslant r_1<p_1\\
x^a\equiv r_2\pmod {p_2},\qquad 0\leqslant r_2<p_2\\
\qquad ......\qquad \qquad \qquad ......\\ x^a\equiv r_j\pmod {p_j},\qquad 0\leqslant r_j<p_j\\ \end{cases} </math>
Заменив <math>x^a</math> на <math>t</math> для удобства, решаем систему относительно <math>t</math> и получаем <math>S</math>.
Применение
Шаблон:Mainref Значительный выигрыш от данного алгоритма можно получить при выполнении умножения. Умножение будет проводится в два раза быстрее при использовании данного алгоритма.
Вычислительная сложность
Шаблон:Mainref Данный метод позволяет сократить количество вычислений в <math>3-4</math> раза. Пусть <math>a</math> имеет длину <math>k</math> бит. При обычном возведении в степень затратится около <math>3k/2</math> умножений по модулю. Пусть мы хотим вычислить <math>(x^a\bmod p,x^a\bmod q)</math>. Сокращая <math>a</math> на <math>p-1</math> и <math>q-1</math> задача сводится к вычислению <math>(x^{a\bmod (p-1)}\bmod p,x^{a\bmod (q-1)}\bmod q)</math>. Каждая степень в данной записи имеет длину <math>k/2</math>. Поэтому каждая операция возведения в степень потребует <math>3k/4</math> операций. Итого потребуется <math>2\cdot 3k/4=3k/2</math> умножений по модулю простого числа <math>p</math> или <math>q</math> вместо изначального умножения по модулю <math>n</math>.
Метод повторяющихся возведения в квадрат и умножения
Описание метода
Шаблон:Mainref Пусть требуется вычислить <math>x^a\bmod n</math>. Представим степень <math>a=a_{j-1}2^{j-1}+a_{j-2}2^{j-2}+...+a_22^{2}+a_12^1+a_0</math>, где <math>a_j=(0,1)</math>
Представим <math>x^a\bmod n</math> в виде:
<math>x^a\bmod n=x^{a_{j-1}2^{j-1}+a_{j-2}2^{j-2}+...+a_22^{2}+a_12^1+a_0}\bmod n=</math>
<math>=(x^2)^{a_{j-1}2^{j-2}+a_{j-2}2^{j-3}+...+a_12^0}x^{a_0}\bmod n=</math>
<math>=((x^2)^2)^{a_{j-1}2^{j-3}+a_{j-2}2^{j-4}+...+a_22^0}(x^2)^{a_1}x^{a_0}\bmod n=</math>
<math>=(...((x^2)^2...)^2)^{a_{j-1}}...(x^8)^{a_3}(x^4)^{a_2}(x^2)^{a_1}x^{a_0}\bmod n</math>
Далее высчитывается значение выражения <math>x^2\bmod n</math> и проводится замена в преобразованном выражении.
Данная операция производится до тех пор пока не будет найден результат.
Применение
Шаблон:Mainref Если <math>n</math> — простое или является произведением двух больших простых чисел, то обычно используют метод повторяющихся возведения в квадрат и умножения. Однако, если <math>n</math> — составное, то обычно используют это метод вместе с китайской теоремой об остатках.
Вычислительная сложность
Шаблон:Mainref Средняя сложность данного алгоритма равна <math>1,5a</math> операций умножения двух <math>a</math>-битовых чисел плюс <math>1,5a</math> операций деления <math>2a</math>-битовых чисел на <math>a</math>-битовое число. Для <math>1000</math>-битовых и более длинных чисел данный алгоритм выполняется на ЭВМ достаточно быстро.
Метод Монтгомери возведения в степень
История
Шаблон:Mainref Данный метод был предложен 1985 году Питером Монтгомери для ускорения выполнения модульного возведения в степень.
Описание метода
Шаблон:Mainref В этом методе каждому числу <math>x</math> ставится в соответствие некоторый образ <math>F(x)</math> и все вычисления производятся с <math>F(x)</math>, а в конце производится переход от образа к числу.
Шаблон:Рамка Теорема(Монтгомери).
Пусть <math>N,R</math> — взаимно простые положительные целые числа, а <math>N'=(-N^{-1})\bmod R</math>. Тогда для любого целого <math>x</math> число <math>y=x+N((xN')\bmod R)</math> делится на <math>R</math>, причем <math>y/R\equiv xR^{-1}(\bmod N)</math>. Более того, если <math>0\leqslant x<RN</math>, то разность <math>y/R-((xR^{-1})\bmod N)</math> равна либо <math>0</math>, либо <math>N</math>. Шаблон:Конец рамки
Данная теорема позволяет вычислить оптимальным способом величину <math> (xR^{-1})\bmod N </math> для некоторого удобно выбранного <math> R </math>.
Шаблон:Рамка Определение 1. Для чисел <math> R </math> , <math> N </math> , <math> x </math> , таких что НОД<math> (R,N) = 1 </math> и <math> 0 \leqslant x < N </math>, назовем <math> (R,N) </math> — остатком числа <math> x </math> величину <math> \overline{x} = (xR)\bmod N </math>. Шаблон:Конец рамки
Шаблон:Рамка Определение 2. Произведением Монтгомери двух целых чисел <math> a </math> , <math> b </math> называется число <math> M(a,b) = abR^{-1} \bmod N </math> Шаблон:Конец рамки
Шаблон:Рамка Теорема (правила Монтгомери). Пусть числа <math> R </math> , <math> N </math> взаимно просты, и <math> 0 \leqslant a,b < N </math>. Тогда <math> a\bmod N = M(\overline{a},1) </math> и <math> M(\overline{a},\overline{b}) = \overline{ab} </math> Шаблон:Конец рамки
То есть, для наглядности, запишем выражение для возведения <math> x </math> в <math> 3 </math> степень: <math> M(M(M(\overline{x},\overline{x}),\overline{x}),1) = x^3 \bmod N </math>
Шаблон:Рамка Алгоритм(Произведение Монтгомери). Пусть заданы целые числа <math>0\leqslant c,d<N</math>, где <math>N</math> нечетно, а <math>R=2^s>N</math>. Этот алгоритм возвращает <math>M(c,d)</math>.
- 1.[Функция M Монтгомери]
- <math>M(c,d)</math>{
- <math>x=cd</math>;
- <math>z=y/z</math>;
- //В соответствии с теоремой(Монтгомери).
- <math>M(c,d)</math>{
- 2.[Поправить результат]
- if <math> (z \geqslant N)z=z-N </math>;
- return <math> z </math>;
- }
Шаблон:Рамка Алгоритм(Метод Монтгомери возведения в степень). Пусть заданы числа <math>0\leqslant x<N</math>, <math>y>0</math>, и <math>R</math> выбрано так же, как для алгоритма(Произведение Монтгомери). Этот алгоритм возвращает <math>x^y\bmod N</math>. Через <math>(y_0,...,y_{D-1})</math> мы обозначаем двоичные биты <math>y</math>.
- 1.[Начальная установка]
- <math>\overline{x}=(xR)\bmod N</math>;
- //С помощью какого-либо метода деления с остатком.
- <math>\overline{p}=R\bmod N</math>;
- //С помощью какого-либо метода деления с остатком.
- <math>\overline{x}=(xR)\bmod N</math>;
- 2.[Схема возведения в степень]
- for <math>(D-1\geqslant j\geqslant 0)</math>{
- <math>\overline{p}=M(\overline{p},\overline{p})</math>;
- //с помощью алгоритма(произведение Монтгомери).
- if <math>(y_i==1)\overline{p}=M(\overline{p},\overline{x})</math>;
- <math>\overline{p}=M(\overline{p},\overline{p})</math>;
- }
- //Теперь <math>\overline{p}</math> равняется <math>\overline{x}^y</math>.
- for <math>(D-1\geqslant j\geqslant 0)</math>{
- 3.[Окончательное получение степени]
- <math>M(\overline{p},1)</math>;
В итоге получаем образ <math>\overline{x}=xR\bmod N</math>, от которого мы можем получить конечный результат <math>x=\overline{x}R^{-1}\bmod N</math>, причем выражение <math>R^{-1}\bmod N</math> вычислено заранее. Для произведения двух чисел результат будет выглядеть как <math> z = \overline{z} R^{-1} \bmod N = \overline{x} \overline{y} R^{-1} \bmod N \equiv \frac{\overline{x} \overline{y} - (\overline{x} \overline{y}(N^{-1} \bmod R)\bmod R) N}{R} \bmod N </math>
Применение
Шаблон:Mainref Данный метод дает выигрыш в производительности по сравнению с методом повторяющихся возведения в квадрат и умножения, так как умножение двух чисел по модулю происходит значительно быстрее.
Вычислительная сложность
Шаблон:Mainref Данный метод позволяет уменьшить (при больших значения <math>N</math>) вычисления функции <math>\operatorname{mod}</math> до одного умножения двух чисел размером <math>N</math>. Сложность умножения Монтгомери оценивается как <math>O(n^2)</math>.
Алгоритм с использованием «школьного» метода
Описание метода
Шаблон:Mainref Для наглядности рассмотрим метод для основания <math> B = 2 </math>, то есть будем проводить вычисления в <math> B </math> — ичной (или двоичной, так как <math> B = 2 </math>) системе счисления. Основание <math> B = 2 </math> имеет плюс, в том что выполнение операции деления на <math> 2 </math> происходит сдвигом вправо, а умножение на <math> 2 </math> — сдвигом влево.
Шаблон:Рамка Определение 1. Представлением неотрицательного целого числа <math> x </math> в системе счисления с основанием <math> B </math> (или <math> B </math>-ичной записью числа <math> x </math>) называется кратчайшая последовательность целых чисел <math> (x_i) </math>, называемых цифрами записи, такая что каждая из этих цифр удовлетворяет неравенству <math> 0\leqslant x_i<B </math>, и выполнено равенство <math> x = \sum_{i=0}^{D-1} x_iB^i </math> Шаблон:Конец рамки
Для примера, рассмотрим двоичный алгоритм взятия <math> \operatorname{mod} </math> от произведения <math> xy </math>.
Шаблон:Рамка Алгоритм (двоичный алгоритм умножения и взятия остатка). Пусть заданы положительные целые числа <math> x </math>, <math> y </math> такие что <math> 0\leqslant x </math>,<math> y<N </math>. Этот алгоритм возвращает результат составной операции <math> (xy) \bmod N </math>. Мы предполагаем, что задано двоичное представление числа <math> x </math> согласно определению 1, так что биты числа <math> x </math> имеют вид <math> (x_0,...,x_{D-1}) </math>, и <math> x_{D-1}>0 </math> — самый старший бит.
- 1.[Начальная установка]
- <math> s = 0 </math>;
- 2.[Преобразовать все <math> D </math> битов]
- for <math>(D-1\geqslant j\geqslant 0) </math> {
- <math> s=2s </math>;
- if <math> (s\geqslant N) s=s-N </math>;
- if <math> (x_j==1)s=s+y </math>;
- if <math> (s\geqslant N)s=s-N </math>;
- }
- return <math> s </math>;
- for <math>(D-1\geqslant j\geqslant 0) </math> {
Данный метод имеет один недостаток: он не использует преимущество многобитовой арифметики, доступной на любой современной ЭВМ. Поэтому обычно используют основания <math> B </math> большие <math> 2 </math>.
Вычислительная сложность «школьного» метода
Шаблон:Mainref Выражения вида <math>a^b(\bmod n)</math> имеет оценку вычислительной сложности — <math>O_s((\log n)^3)</math>
См. также
Примечания
Литература
