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

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

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

Пусть требуется вычислить ${\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 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}$ .

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

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

Пусть требуется вычислить ${\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 n}$ — простое или является произведением двух больших простых чисел, то обычно используют метод повторяющихся возведения в квадрат и умножения. Однако, если ${\displaystyle n}$ — составное, то обычно используют это метод вместе с китайской теоремой об остатках.

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

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

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

История

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

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

В этом методе каждому числу ${\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}$ ) вычисления функции ${\displaystyle \operatorname {mod} }$ до одного умножения двух чисел размером ${\displaystyle N}$ . Сложность умножения Монтгомери оценивается как ${\displaystyle O(n^{2})}$ .

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

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

Для наглядности рассмотрим метод для основания ${\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}$ .

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

Выражения вида ${\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