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

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

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


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


 Пусть требуется вычислить S=xamodnS=xamodn, где числа x,a,nx,a,n достаточнобольшие и пусть модуль может быть разложен на простые делителиn=p1p2...pjn=p1p2...pj. Тогда для быстрого возведения в степень по модулюможно воспользоваться китайской теоремой об остатках и решить системууравнений (предварительно посчитав вычеты xari(modpi)xari(modpi) сиспользованием теоремы Ферма, где i=1,2,...,ji=1,2,...,j):
 $\begin{cases}x^a\equiv r_1\pmod {p_1},\qquad 0\leqslant r_1 x^a\equiv r_2\pmod {p_2},\qquad 0\leqslant r_2 \qquad ......\qquad \qquad \qquad ......\\x^a\equiv r_j\pmod {p_j},\qquad 0\leqslant r_j Заменив xaxa на tt для удобства, решаем систему относительно tt иполучаем SS.

Применение


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

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


 Данный метод позволяет сократить количество вычислений в 3434 раза.Пусть aa имеет длину kk бит. При обычном возведении в степеньзатратится около 3k/23k/2 умножений по модулю. Пусть мы хотим вычислить(xamodp,xamodq)(xamodp,xamodq). Сокращая aa на p1p1 и q1q1 задача сводитсяк вычислению (xamod(p1)modp,xamod(q1)modq)(xamod(p1)modp,xamod(q1)modq). Каждаястепень в данной записи имеет длину k/2k/2. Поэтому каждая операциявозведения в степень потребует 3k/43k/4 операций. Итого потребуется23k/4=3k/223k/4=3k/2 умножений по модулю простого числа pp или qq вместоизначального умножения по модулю nn.

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


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


 Пусть требуется вычислить xamodnxamodn. Представим степеньa=aj12j1+aj22j2+...+a222+a121+a0a=aj12j1+aj22j2+...+a222+a121+a0, гдеaj=(0,1)aj=(0,1)
 Представим xamodnxamodn в виде:
xamodn=xaj12j1+aj22j2+...+a222+a121+a0modn=xamodn=xaj12j1+aj22j2+...+a222+a121+a0modn=
=(x2)aj12j2+aj22j3+...+a120xa0modn==(x2)aj12j2+aj22j3+...+a120xa0modn=
=((x2)2)aj12j3+aj22j4+...+a220(x2)a1xa0modn==((x2)2)aj12j3+aj22j4+...+a220(x2)a1xa0modn=
=(...((x2)2...)2)aj1...(x8)a3(x4)a2(x2)a1xa0modn=(...((x2)2...)2)aj1...(x8)a3(x4)a2(x2)a1xa0modn
 Далее высчитывается значение выражения x2modnx2modn и проводится заменав преобразованном выражении.
 Данная операция производится до тех пор пока не будет найден результат.

Применение


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

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


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

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


История


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

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


 В этом методе каждому числу xx ставится в соответствие некоторый образF(x)F(x) и все вычисления производятся с F(x)F(x), а в конце производитсяпереход от образа к числу.
Теорема(Монтгомери).
 Пусть N,RN,R — взаимно простые положительные целые числа, аN=(N1)modRN=(N1)modR. Тогда для любого целого xx числоy=x+N((xN)modR)y=x+N((xN)modR) делится на RR, причемy/RxR1(modN)y/RxR1(modN). Более того, если $0\leqslant x Данная теорема позволяет вычислить оптимальным способом величину(xR1)modN(xR1)modN для некоторого удобно выбранного RR.
Определение 1. Для чисел RR , NN , xx , таких чтоНОД(R,N)=1(R,N)=1 и 0x<N0x<N, назовем (R,N)(R,N) — остатком числаxx величину ¯x=(xR)modNx¯¯¯=(xR)modN.
Определение 2. Произведением Монтгомери двух целых чисел aa ,bb называется число M(a,b)=abR1modNM(a,b)=abR1modN
Теорема (правила Монтгомери). Пусть числа RR , NN взаимнопросты, и 0a,b<N0a,b<N. Тогда amodN=M(¯a,1)amodN=M(a¯¯¯,1) иM(¯a,¯b)=¯abM(a¯¯¯,b¯¯)=ab¯¯¯¯¯
 То есть, для наглядности, запишем выражение для возведения xx в 33степень:M(M(M(¯x,¯x),¯x),1)=x3modNM(M(M(x¯¯¯,x¯¯¯),x¯¯¯),1)=x3modN
Алгоритм(Произведение Монтгомери). Пусть заданы целые числа$0\leqslant c,dN.Этоталгоритмвозвращает.ЭтоталгоритмвозвращаетM(c,d).1.[ФункцияMМонтгомери].1.[ФункцияMМонтгомери]M(c,d){{x=cd;;z=y/z$;

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

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


 if (zN)z=zN(zN)z=zN;
 return zz;

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

 //с помощью алгоритма(произведение Монтгомери).
 if (yi==1)¯p=M(¯p,¯x);
 \}

 //Теперь ¯p равняется ¯xy.

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

M(¯p,1);

 В итоге получаем образ ¯x=xRmodN, от которого мы можемполучить конечный результат x=¯xR1modN, причемвыражение R1modN вычислено заранее. Для произведения двух чиселрезультат будет выглядеть какz=¯zR1modN=¯x¯yR1modN¯x¯y(¯x¯y(N1modR)modR)NRmodN

Применение


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

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


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

Метод с использованием функцииЭйлера


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


 Если возводить x, лежащий в пределах от 0 до p (где p — любоепростое число), в степень p1, то можно быстро найти значениеискомого выражения в виде 1(modp).
xp1=1(modp), 0<x<p
 Тот же результат можно получить, если степень является функцией Эйлераf(x)=(p1)(q1), где p и q — простые числа

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


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


 Для наглядности рассмотрим метод для основания B=2, то есть будемпроводить вычисления в B — ичной (или двоичной, так как B=2)системе счисления. Основание B=2 имеет плюс, в том что выполнениеоперации деления на 2 происходит сдвигом вправо, а умножение на2 — сдвигом влево.
Определение 1. Представлением неотрицательного целого числа xв системе счисления с основанием B (или B-ичной записью числа x)называется кратчайшая последовательность целых чисел (xi), называемыхцифрами записи, такая что каждая из этих цифр удовлетворяет неравенству$0\leqslant x_i Для примера, рассмотрим двоичный алгоритм взятия mod от произведенияxy.
Алгоритм (двоичный алгоритм умножения и взятия остатка). Пустьзаданы положительные целые числа x, y такие что0x,$yопределению 1, так что битычисла x имеют вид (x0,...,xD1), и xD1>0 — самый старшийбит.

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

s=0;
 2.[Преобразовать все D битов]

 for (D1j0) \{

s=2s;
 if (sN)s=sN;
 if (xj==1)s=s+y;
 if (sN)s=sN;
 \}
 return s;

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

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


 Выражения вида ab(modn) имеет оценку вычислительной сложности —Os((logn)3)