Алгоритмы быстрого возведения в степень по модулю

Алгоритмы быстрого возведения в степень по модулю — разновидность алгоритмов возведения в степень по модулю, широко использующихся в различных криптосистемах, для ускорения вычислительных операций с большими числами.

Метод с использованием Китайской теоремы об остатках

Основная статья: Китайская теорема об остатках

Описание метода

Основной источник: Теоретический минимум и алгоритмы цифровой подписи, 2010, с. 55-56

Пусть требуется вычислить $S=x^{a}{\bmod {n}}$, где числа $x,a,n$ достаточно большие и пусть модуль может быть разложен на простые делители $n=p_{1}p_{2}...p_{j}$. Тогда для быстрого возведения в степень по модулю можно воспользоваться китайской теоремой об остатках и решить систему уравнений (предварительно посчитав вычеты $x^{a}\equiv r_{i}{\pmod {p_{i}}}$ с использованием теоремы Ферма, где $i=1,2,...,j$):

${\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}}$

Заменив $x^{a}$ на $t$ для удобства, решаем систему относительно $t$ и получаем $S$.

Пример

Пусть требуется вычислить $S=3^{5}{\bmod {3}}0$

${\begin{cases}t=3^{5}\equiv 1{\pmod {2}}\\t=3^{5}\equiv 0{\pmod {3}}\\t=3^{5}\equiv 3{\pmod {5}}\\\end{cases}}$

Представим систему в виде

${\begin{cases}t=3^{5}=1+2u\\t=3^{5}=0+3v\\t=3^{5}=3+5w\\\end{cases}}$

Подставив t из первого уравнения во второе, получим $1+2u\equiv 0{\pmod {3}}$, тогда $2u\equiv 2{\pmod {3}}$, или $u\equiv 1{\pmod {3}}$, или $u=1+3h$;

подставив затем t из первого уравнения в третье с учетом выражения для $u$ получим $1+2(1+3h)\equiv 3{\pmod {5}}$ или $6h\equiv 0{\pmod {5}}$, тогда $h=0{\pmod {5}}$;

тогда $t=3^{5}\equiv 1+2(1+3\cdot 0)\equiv 3{\pmod {5}}$ следовательно, $S=3^{5}{\bmod {5}}=3$;

Применение

Основной источник: Практическая криптография, 2004, с. 249

Значительный выигрыш от данного алгоритма можно получить при выполнении умножения. Умножение будет проводится в два раза быстрее при использовании данного алгоритма.

Вычислительная сложность

Основной источник: Практическая криптография, 2004, с. 249

Данный метод позволяет сократить количество вычислений в $3-4$ раза. Пусть $a$ имеет длину $k$ бит. При обычном возведении в степень затратится около $3k/2$ умножений по модулю. Пусть мы хотим вычислить $(x^{a}{\bmod {p}},x^{a}{\bmod {q}})$. Сокращая $a$ на $p-1$ и $q-1$ задача сводится к вычислению $(x^{a{\bmod {(}}p-1)}{\bmod {p}},x^{a{\bmod {(}}q-1)}{\bmod {q}})$. Каждая степень в данной записи имеет длину $k/2$. Поэтому каждая операция возведения в степень потребует $3k/4$ операций. Итого потребуется $2\cdot 3k/4=3k/2$ умножений по модулю простого числа $p$ или $q$ вместо изначального умножения по модулю $n$.

Метод повторяющихся возведения в квадрат и умножения

Основная статья: Алгоритм быстрого возведения в степень

Пример блок-схемы метода повторяющихся возведения в квадрат и умножения

Описание метода

Основной источник: Теоретический минимум и алгоритмы цифровой подписи, 2010, с. 56-57

Пусть требуется вычислить $x^{a}{\bmod {n}}$. Представим степень $a=a_{j-1}2^{j-1}+a_{j-2}2^{j-2}+...+a_{2}2^{2}+a_{1}2^{1}+a_{0}$, где $a_{j}=(0,1)$

Представим $x^{a}{\bmod {n}}$ в виде:

$x^{a}{\bmod {n}}=x^{a_{j-1}2^{j-1}+a_{j-2}2^{j-2}+...+a_{2}2^{2}+a_{1}2^{1}+a_{0}}{\bmod {n}}=$

$=(x^{2})^{a_{j-1}2^{j-2}+a_{j-2}2^{j-3}+...+a_{1}2^{0}}x^{a_{0}}{\bmod {n}}=$

$=((x^{2})^{2})^{a_{j-1}2^{j-3}+a_{j-2}2^{j-4}+...+a_{2}2^{0}}(x^{2})^{a_{1}}x^{a_{0}}{\bmod {n}}=$

$=(...((x^{2})^{2}...)^{2})^{a_{j-1}}...(x^{8})^{a_{3}}(x^{4})^{a_{2}}(x^{2})^{a_{1}}x^{a_{0}}{\bmod {n}}$

Далее высчитывается значение выражения $x^{2}{\bmod {n}}$ и проводится замена в преобразованном выражении.

Данная операция производится до тех пор пока не будет найден результат.

Пример

Пусть требуется вычислить $249^{321}{\bmod {4}}99$. Представим степень в виде $321=256+64+1=2^{8}+2^{6}+2^{0}$. Представим $249^{321}{\bmod {4}}99$ в виде $249^{321}{\bmod {4}}99=249^{2^{8}+2^{6}+2^{0}}{\bmod {4}}99=$

$=(((((((249^{2})^{2})^{2})^{2})^{2})^{2})^{2})^{2}(((((249^{2})^{2})^{2})^{2})^{2})^{2}249{\bmod {4}}99=[249^{2}\equiv 125({\bmod {4}}99)]=$

$=((((((125^{2})^{2})^{2})^{2})^{2})^{2})^{2}((((125^{2})^{2})^{2})^{2})^{2}249{\bmod {4}}99=[125^{2}\equiv 156({\bmod {4}}99)]=$

$=(((((156^{2})^{2})^{2})^{2})^{2})^{2}(((156^{2})^{2})^{2})^{2}249{\bmod {4}}99=[156^{2}\equiv 384({\bmod {4}}99)]=$

$=((((384^{2})^{2})^{2})^{2})^{2}((384^{2})^{2})^{2}249{\bmod {4}}99=[384^{2}\equiv 251({\bmod {4}}99)]=$

$=(((251^{2})^{2})^{2})^{2}(251^{2})^{2}249{\bmod {4}}99=[251^{2}\equiv 127({\bmod {4}}99)]=$

$=((127^{2})^{2})^{2}127^{2}249{\bmod {4}}99=[127^{2}\equiv 161({\bmod {4}}99)]=$

$=(161^{2})^{2}161*249{\bmod {4}}99=[161^{2}\equiv 472({\bmod {4}}99)]=$

$=472^{2}161*249{\bmod {4}}99=[472^{2}\equiv 230({\bmod {4}}99)]=$

$=230*161*249{\bmod {4}}99=447$

Применение

Основной источник: Теоретический минимум и алгоритмы цифровой подписи, 2010, с. 56

Если $n$ — простое или является произведением двух больших простых чисел, то обычно используют метод повторяющихся возведения в квадрат и умножения. Однако, если $n$ — составное, то обычно используют это метод вместе с китайской теоремой об остатках.

Вычислительная сложность

Основной источник: Теоретический минимум и алгоритмы цифровой подписи, 2010, с. 57

Средняя сложность данного алгоритма равна $1,5a$ операций умножения двух $a$-битовых чисел плюс $1,5a$ операций деления $2a$-битовых чисел на $a$-битовое число. Для $1000$-битовых и более длинных чисел данный алгоритм выполняется на ЭВМ достаточно быстро.

Метод Монтгомери возведения в степень

Основная статья: Алгоритм Монтгомери

История

Основной источник: Простые числа: Криптографические и вычислительные аспекты, 2011, с. 503

Данный метод был предложен 1985 году Питером Монтгомери для ускорения выполнения модульного возведения в степень.

Описание метода

Основной источник: Простые числа: Криптографические и вычислительные аспекты, 2011, с. 503-505

В этом методе каждому числу $x$ ставится в соответствие некоторый образ $F(x)$ и все вычисления производятся с $F(x)$, а в конце производится переход от образа к числу.

Теорема(Монтгомери). Пусть $N,R$ — взаимно простые положительные целые числа, а $N'=(-N^{-1}){\bmod {R}}$. Тогда для любого целого $x$ число $y=x+N((xN'){\bmod {R}})$ делится на $R$, причем $y/R\equiv xR^{-1}({\bmod {N}})$. Более того, если $0\leqslant x<RN$, то разность $y/R-((xR^{-1}){\bmod {N}})$ равна либо $0$, либо $N$.

Данная теорема позволяет вычислить оптимальным способом величину $(xR^{-1}){\bmod {N}}$ для некоторого удобно выбранного $R$.

Определение 1. Для чисел $R$ , $N$ , $x$ , таких что НОД$(R,N)=1$ и $0\leqslant x<N$, назовем $(R,N)$ — остатком числа $x$ величину ${\overline {x}}=(xR){\bmod {N}}$.

Определение 2. Произведением Монтгомери двух целых чисел $a$ , $b$ называется число $M(a,b)=abR^{-1}{\bmod {N}}$

Теорема (правила Монтгомери). Пусть числа $R$ , $N$ взаимно просты, и $0\leqslant a,b<N$. Тогда $a{\bmod {N}}=M({\overline {a}},1)$ и $M({\overline {a}},{\overline {b}})={\overline {ab}}$

То есть, для наглядности, запишем выражение для возведения $x$ в $3$ степень: $M(M(M({\overline {x}},{\overline {x}}),{\overline {x}}),1)=x^{3}{\bmod {N}}$

Алгоритм(Произведение Монтгомери). Пусть заданы целые числа $0\leqslant c,d<N$, где $N$ нечетно, а $R=2^{s}>N$. Этот алгоритм возвращает $M(c,d)$. 1.[Функция M Монтгомери] $M(c,d)${ $x=cd$; $z=y/z$; //В соответствии с теоремой(Монтгомери). 2.[Поправить результат] if $(z\geqslant N)z=z-N$; return $z$; }

Алгоритм(Метод Монтгомери возведения в степень). Пусть заданы числа $0\leqslant x<N$, $y>0$, и $R$ выбрано так же, как для алгоритма(Произведение Монтгомери). Этот алгоритм возвращает $x^{y}{\bmod {N}}$. Через $(y_{0},...,y_{D-1})$ мы обозначаем двоичные биты $y$. 1.[Начальная установка] ${\overline {x}}=(xR){\bmod {N}}$; //С помощью какого-либо метода деления с остатком. ${\overline {p}}=R{\bmod {N}}$; //С помощью какого-либо метода деления с остатком. 2.[Схема возведения в степень] for $(D-1\geqslant j\geqslant 0)${ ${\overline {p}}=M({\overline {p}},{\overline {p}})$; //с помощью алгоритма(произведение Монтгомери). if $(y_{i}==1){\overline {p}}=M({\overline {p}},{\overline {x}})$; } //Теперь ${\overline {p}}$ равняется ${\overline {x}}^{y}$. 3.[Окончательное получение степени] $M({\overline {p}},1)$;

В итоге получаем образ ${\overline {x}}=xR{\bmod {N}}$, от которого мы можем получить конечный результат $x={\overline {x}}R^{-1}{\bmod {N}}$, причем выражение $R^{-1}{\bmod {N}}$ вычислено заранее. Для произведения двух чисел результат будет выглядеть как $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}}$

Пример

Пусть $N=11$, $b=R=2^{5}=32>N$ и хотим перемножить два числа $x=3$ и $x=3$ (т.е. возвести $x$ в квадрат)

$3$ имеет образ $3\cdot R{\bmod {N}}=96{\bmod {1}}1=8$

(для проверки $9$ имеет образ $9\cdot R{\bmod {N}}=288{\bmod {1}}1=2$)

Перемножаем образы:

$w={\overline {x}}\cdot {\overline {x}}=64$,

Производим переход от образа умножения к искомому прообразу

$q=N^{-1}{\bmod {R}}=3$,

$u=-w\cdot q{\bmod {R}}=-64\cdot 3{\bmod {3}}2=-192{\bmod {3}}2=0$,

${\overline {z}}=(w+u\cdot N)/R=(64+0\cdot 32)/32=2$

Соответственно прообраз $z={\overline {z}}\cdot R^{-1}{\bmod {N}}=2\cdot 32^{-1}{\bmod {1}}1=9$

Применение

Основной источник: Простые числа: Криптографические и вычислительные аспекты, 2011, с. 505

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

Вычислительная сложность

Основной источник: Простые числа: Криптографические и вычислительные аспекты, 2011, с. 505

Данный метод позволяет уменьшить (при больших значения $N$) вычисления функции $\operatorname {mod}$ до одного умножения двух чисел размером $N$. Сложность умножения Монтгомери оценивается как $O(n^{2})$.

Алгоритм с использованием «школьного» метода

Описание метода

Основной источник: Простые числа: Криптографические и вычислительные аспекты, 2011, с. 500-502

Для наглядности рассмотрим метод для основания $B=2$, то есть будем проводить вычисления в $B$ — ичной (или двоичной, так как $B=2$) системе счисления. Основание $B=2$ имеет плюс, в том что выполнение операции деления на $2$ происходит сдвигом вправо, а умножение на $2$ — сдвигом влево.

Определение 1. Представлением неотрицательного целого числа $x$ в системе счисления с основанием $B$ (или $B$-ичной записью числа $x$) называется кратчайшая последовательность целых чисел $(x_{i})$, называемых цифрами записи, такая что каждая из этих цифр удовлетворяет неравенству $0\leqslant x_{i}<B$, и выполнено равенство $x=\sum _{i=0}^{D-1}x_{i}B^{i}$

Для примера, рассмотрим двоичный алгоритм взятия $\operatorname {mod}$ от произведения $xy$.

Алгоритм (двоичный алгоритм умножения и взятия остатка). Пусть заданы положительные целые числа $x$, $y$ такие что $0\leqslant x$,$y<N$. Этот алгоритм возвращает результат составной операции $(xy){\bmod {N}}$. Мы предполагаем, что задано двоичное представление числа $x$ согласно определению 1, так что биты числа $x$ имеют вид $(x_{0},...,x_{D-1})$, и $x_{D-1}>0$ — самый старший бит. 1.[Начальная установка] $s=0$; 2.[Преобразовать все $D$ битов] for $(D-1\geqslant j\geqslant 0)$ { $s=2s$; if $(s\geqslant N)s=s-N$; if $(x_{j}==1)s=s+y$; if $(s\geqslant N)s=s-N$; } return $s$;

Данный метод имеет один недостаток: он не использует преимущество многобитовой арифметики, доступной на любой современной ЭВМ. Поэтому обычно используют основания $B$ большие $2$.

Вычислительная сложность «школьного» метода

Основной источник: Простые числа: Криптографические и вычислительные аспекты, 2011, с. 137

Выражения вида $a^{b}({\bmod {n}})$ имеет оценку вычислительной сложности — $O_{s}((\log n)^{3})$

См. также

• Возведение в степень по модулю
• Алгоритмы быстрого возведения в степень

Литература

• Крэндалл Ричард, Померанс Карл. Простые числа: Криптографические и вычислительные аспекты / Под ред. и с предисл. В. Н. Чубарикова.. — М.: УРСС:: Книжный Дом «ЛИБРОКОМ», 2011. — 664 с. — ISBN 978-5-453-00016-6, 978-5-397-03060-2.
• Молдовян Н. А. Теоретический минимум и алгоритмы цифровой подписи. — СПб.: БВХ-Петербург: Книжный Дом «ЛИБРОКОМ», 2010. — 304 с. — ISBN 978-5-9775-0585-7.
• Фергюнсон, Нильс, Шнайер, Брюс. Практическая криптография. — M.: Издательский дом «Вильямс», 2004. — 432 с. — ISBN 5-8459-0733-0.
• Мао В. Современная криптография: Теория и практика / пер. Д. А. Клюшина — М.: Вильямс, 2005. — 768 с. — ISBN 978-5-8459-0847-6