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

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

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


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


 Пусть требуется вычислить 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) — остатком числа x величину ¯x=(xR)modN.
Определение 2. Произведением Монтгомери двух целых чисел a , b называется число M(a,b)=abR1modN
Теорема (правила Монтгомери). Пусть числа R , N взаимно просты, и 0a,b<N. Тогда amodN=M(¯a,1) и M(¯a,¯b)=¯ab
 То есть, для наглядности, запишем выражение для возведения x в 3 степень: M(M(M(¯x,¯x),¯x),1)=x3modN
Алгоритм(Произведение Монтгомери). Пусть заданы целые числа $0\leqslant c,dN.ЭтоталгоритмвозвращаетM(c,d).1.[ФункцияMМонтгомери]M(c,d){x=cd;z=y/z$;

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

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


  if (zN)z=zN;
 return z;

Алгоритм(Метод Монтгомери возведения в степень). Пусть заданы числа $0\leqslant x0,и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 (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)