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

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

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

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

Шаблон:Mainref Пусть требуется вычислить $S=x^{a}modn$, где числа $x,a,n$ достаточно большие и пусть модуль может быть разложен на простые делители $n=p_1{p}_2...p_j$. Тогда для быстрого возведения в степень по модулю можно воспользоваться китайской теоремой об остатках и решить систему уравнений (предварительно посчитав вычеты $x^a\equiv r_i(\mathrm{mod}{p}_i)$ с использованием теоремы Ферма, где $i=1,2,...,j$):

$\{\begin{array}{c}{x}^a\equiv r_1(\mathrm{mod}{p}_1),0⩽r_1<p_1\\ x^a\equiv r_2(\mathrm{mod}{p}_2),0⩽r_2<p_2\\ ............\\ x^a\equiv r_j(\mathrm{mod}{p}_j),0⩽r_j<p_j\end{array}$

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

Применение

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

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

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

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

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

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

Шаблон:Mainref Пусть требуется вычислить $x^{a}modn$. Представим степень $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}modn$ в виде:

$x^{a}modn=x^{a_{j-1}{2}^{j-1}+a_{j-2}{2}^{j-2}+...+a_2{2}^2+a_1{2}^1+a_0}modn=$

$=(x^2{)}^{a_{j-1}{2}^{j-2}+a_{j-2}{2}^{j-3}+...+a_1{2}^0}{x}^{a_0}modn=$

$=((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}modn=$

$=(...((x^2{)}^2...{)}^2{)}^{a_{j-1}}...(x^8{)}^{a_3}(x^4{)}^{a_2}(x^2{)}^{a_1}{x}^{a_0}modn$

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

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

Применение

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

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

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

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

История

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

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

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

Шаблон:Рамка Теорема(Монтгомери).

Пусть $N,R$ — взаимно простые положительные целые числа, а $N^{\prime }=(-N^{-1})modR$. Тогда для любого целого $x$ число $y=x+N((x{N}^{\prime })modR)$ делится на $R$, причем $y/R\equiv x{R}^{-1}(modN)$. Более того, если $0⩽x<RN$, то разность $y/R-((x{R}^{-1})modN)$ равна либо $0$, либо $N$. Шаблон:Конец рамки

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

Шаблон:Рамка Определение 1. Для чисел $R$ , $N$ , $x$ , таких что НОД$(R,N)=1$ и $0⩽x<N$, назовем $(R,N)$ — остатком числа $x$ величину $\bar{x}=(xR)modN$. Шаблон:Конец рамки

Шаблон:Рамка Определение 2. Произведением Монтгомери двух целых чисел $a$ , $b$ называется число $M(a,b)=ab{R}^{-1}modN$ Шаблон:Конец рамки

Шаблон:Рамка Теорема (правила Монтгомери). Пусть числа $R$ , $N$ взаимно просты, и $0⩽a,b<N$. Тогда $amodN=M(\bar{a},1)$ и $M(\bar{a},\bar{b})=\overline{ab}$ Шаблон:Конец рамки

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

Шаблон:Рамка Алгоритм(Произведение Монтгомери). Пусть заданы целые числа $0⩽c,d<N$, где $N$ нечетно, а $R=2^s>N$. Этот алгоритм возвращает $M(c,d)$.

1.[Функция M Монтгомери]

$M(c,d)${

$x=cd$;

$z=y/z$;

//В соответствии с теоремой(Монтгомери).

2.[Поправить результат]

if $(z⩾N)z=z-N$;

return $z$;

}

Шаблон:Рамка Алгоритм(Метод Монтгомери возведения в степень). Пусть заданы числа $0⩽x<N$, $y>0$, и $R$ выбрано так же, как для алгоритма(Произведение Монтгомери). Этот алгоритм возвращает $x^{y}modN$. Через $(y_0,...,y_{D-1})$ мы обозначаем двоичные биты $y$.

1.[Начальная установка]

$\bar{x}=(xR)modN$;

//С помощью какого-либо метода деления с остатком.

$\bar{p}=RmodN$;

//С помощью какого-либо метода деления с остатком.

2.[Схема возведения в степень]

for $(D-1⩾j⩾0)${

$\bar{p}=M(\bar{p},\bar{p})$;

//с помощью алгоритма(произведение Монтгомери).

if $(y_i==1)\bar{p}=M(\bar{p},\bar{x})$;

}

//Теперь $\bar{p}$ равняется $\stackrel{y}{\stackrel{‾}{x}}$.

3.[Окончательное получение степени]

$M(\bar{p},1)$;

В итоге получаем образ $\bar{x}=xRmodN$, от которого мы можем получить конечный результат $x=\bar{x}{R}^{-1}modN$, причем выражение $R^{-1}modN$ вычислено заранее. Для произведения двух чисел результат будет выглядеть как $z=\bar{z}{R}^{-1}modN=\bar{x}\bar{y}{R}^{-1}modN\equiv \frac{\bar{x}\bar{y}-(\bar{x}\bar{y}(N^{-1}modR)modR)N}{R}modN$

Применение

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

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

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

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

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

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

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

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

Шаблон:Рамка Алгоритм (двоичный алгоритм умножения и взятия остатка). Пусть заданы положительные целые числа $x$, $y$ такие что $0⩽x$,$y<N$. Этот алгоритм возвращает результат составной операции $(xy)modN$. Мы предполагаем, что задано двоичное представление числа $x$ согласно определению 1, так что биты числа $x$ имеют вид $(x_0,...,x_{D-1})$, и $x_{D-1}>0$ — самый старший бит.

1.[Начальная установка]

$s=0$;

2.[Преобразовать все $D$ битов]

for $(D-1⩾j⩾0)$ {

$s=2s$;

if $(s⩾N)s=s-N$;

if $(x_j==1)s=s+y$;

if $(s⩾N)s=s-N$;

}

return $s$;

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

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

Шаблон:Mainref Выражения вида $a^b(modn)$ имеет оценку вычислительной сложности — $O_s((\log n{)}^3)$

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Source