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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

Применение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

${\displaystyle =(((((((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)]=}$

${\displaystyle =((((((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)]=}$

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

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

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

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

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

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

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

Применение

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

Применение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выражения вида ${\displaystyle a^{b}({\bmod {n}})}$ имеет оценку вычислительной сложности — ${\displaystyle 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