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

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

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

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

Описание методаПравить

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

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

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

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

Пример

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

$\{\begin{array}{l}t=3^5\equiv <!--\; \equiv \; -->1(\mathrm{mod}2)\\ t=3^5\equiv <!--\; \equiv \; -->0(\mathrm{mod}3)\\ t=3^5\equiv <!--\; \equiv \; -->3(\mathrm{mod}5)\end{array}$${\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}}$ 

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

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

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

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

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

ПрименениеПравить

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

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

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

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

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

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

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

 

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

Описание методаПравить

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

Пусть требуется вычислить $x^{a}modn$$x^{a}{\bmod {n}}$ . Представим степень $a=a_{j-<!--\; -\; -->1}{2}^{j-<!--\; -\; -->1}+a_{j-<!--\; -\; -->2}{2}^{j-<!--\; -\; -->2}+...+a_2{2}^2+a_1{2}^1+a_0$$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)$$a_{j}=(0,1)$ 

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

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

$=(x^2{)}^{a_{j-<!--\; -\; -->1}{2}^{j-<!--\; -\; -->2}+a_{j-<!--\; -\; -->2}{2}^{j-<!--\; -\; -->3}+...+a_1{2}^0}{x}^{a_0}modn=$$=(x^{2})^{a_{j-1}2^{j-2}+a_{j-2}2^{j-3}+...+a_{1}2^{0}}x^{a_{0}}{\bmod {n}}=$ 

$=((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})^{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}}=$ 

$=(...((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})^{2}...)^{2})^{a_{j-1}}...(x^{8})^{a_{3}}(x^{4})^{a_{2}}(x^{2})^{a_{1}}x^{a_{0}}{\bmod {n}}$ 

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

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

Пример

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

$=((((((({249}^2{)}^2{)}^2{)}^2{)}^2{)}^2{)}^2{)}^2((((({249}^2{)}^2{)}^2{)}^2{)}^2{)}^{2}249mod499=[{249}^2\equiv <!--\; \equiv \; -->125(mod499)]=$$=(((((((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)]=$ 

$=(((((({125}^2{)}^2{)}^2{)}^2{)}^2{)}^2{)}^2(((({125}^2{)}^2{)}^2{)}^2{)}^{2}249mod499=[{125}^2\equiv <!--\; \equiv \; -->156(mod499)]=$$=((((((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)]=$ 

$=((((({156}^2{)}^2{)}^2{)}^2{)}^2{)}^2((({156}^2{)}^2{)}^2{)}^{2}249mod499=[{156}^2\equiv <!--\; \equiv \; -->384(mod499)]=$$=(((((156^{2})^{2})^{2})^{2})^{2})^{2}(((156^{2})^{2})^{2})^{2}249{\bmod {4}}99=[156^{2}\equiv 384({\bmod {4}}99)]=$ 

$=(((({384}^2{)}^2{)}^2{)}^2{)}^2(({384}^2{)}^2{)}^{2}249mod499=[{384}^2\equiv <!--\; \equiv \; -->251(mod499)]=$$=((((384^{2})^{2})^{2})^{2})^{2}((384^{2})^{2})^{2}249{\bmod {4}}99=[384^{2}\equiv 251({\bmod {4}}99)]=$ 

$=((({251}^2{)}^2{)}^2{)}^2({251}^2{)}^{2}249mod499=[{251}^2\equiv <!--\; \equiv \; -->127(mod499)]=$$=(((251^{2})^{2})^{2})^{2}(251^{2})^{2}249{\bmod {4}}99=[251^{2}\equiv 127({\bmod {4}}99)]=$ 

$=(({127}^2{)}^2{)}^2{127}^{2}249mod499=[{127}^2\equiv <!--\; \equiv \; -->161(mod499)]=$$=((127^{2})^{2})^{2}127^{2}249{\bmod {4}}99=[127^{2}\equiv 161({\bmod {4}}99)]=$ 

$=({161}^2{)}^{2}161\ast <!--\; \ast \; -->249mod499=[{161}^2\equiv <!--\; \equiv \; -->472(mod499)]=$$=(161^{2})^{2}161*249{\bmod {4}}99=[161^{2}\equiv 472({\bmod {4}}99)]=$ 

$={472}^{2}161\ast <!--\; \ast \; -->249mod499=[{472}^2\equiv <!--\; \equiv \; -->230(mod499)]=$$=472^{2}161*249{\bmod {4}}99=[472^{2}\equiv 230({\bmod {4}}99)]=$ 

$=230\ast <!--\; \ast \; -->161\ast <!--\; \ast \; -->249mod499=447$$=230*161*249{\bmod {4}}99=447$ 

ПрименениеПравить

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

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

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

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

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

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

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

ИсторияПравить

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

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

Описание методаПравить

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

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

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

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

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

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

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

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

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

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

В итоге получаем образ $\stackrel{¯<!--\; ¯\; -->}{x}=xRmodN$${\overline {x}}=xR{\bmod {N}}$ , от которого мы можем получить конечный результат $x=\stackrel{¯<!--\; ¯\; -->}{x}{R}^{-<!--\; -\; -->1}modN$$x={\overline {x}}R^{-1}{\bmod {N}}$ , причем выражение $R^{-<!--\; -\; -->1}modN$$R^{-1}{\bmod {N}}$  вычислено заранее. Для произведения двух чисел результат будет выглядеть как $z=\stackrel{¯<!--\; ¯\; -->}{z}{R}^{-<!--\; -\; -->1}modN=\stackrel{¯<!--\; ¯\; -->}{x}\stackrel{¯<!--\; ¯\; -->}{y}{R}^{-<!--\; -\; -->1}modN\equiv <!--\; \equiv \; -->\frac{\stackrel{¯<!--\; ¯\; -->}{x}\stackrel{¯<!--\; ¯\; -->}{y}-<!--\; -\; -->(\stackrel{¯<!--\; ¯\; -->}{x}\stackrel{¯<!--\; ¯\; -->}{y}(N^{-<!--\; -\; -->1}modR)modR)N}{R}modN$$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}}$ 

Пример

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

$3$$3$  имеет образ $3\cdot <!--\; \cdot \; -->RmodN=96mod11=8$$3\cdot R{\bmod {N}}=96{\bmod {1}}1=8$ 

(для проверки $9$$9$  имеет образ $9\cdot <!--\; \cdot \; -->RmodN=288mod11=2$$9\cdot R{\bmod {N}}=288{\bmod {1}}1=2$ )

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

$w=\stackrel{¯<!--\; ¯\; -->}{x}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x}=64$$w={\overline {x}}\cdot {\overline {x}}=64$ ,

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

$q=N^{-<!--\; -\; -->1}modR=3$$q=N^{-1}{\bmod {R}}=3$ ,

$u=-<!--\; -\; -->w\cdot <!--\; \cdot \; -->qmodR=-<!--\; -\; -->64\cdot <!--\; \cdot \; -->3mod32=-<!--\; -\; -->192mod32=0$$u=-w\cdot q{\bmod {R}}=-64\cdot 3{\bmod {3}}2=-192{\bmod {3}}2=0$ ,

$\stackrel{¯<!--\; ¯\; -->}{z}=(w+u\cdot <!--\; \cdot \; -->N)/R=(64+0\cdot <!--\; \cdot \; -->32)/32=2$${\overline {z}}=(w+u\cdot N)/R=(64+0\cdot 32)/32=2$ 

Соответственно прообраз $z=\stackrel{¯<!--\; ¯\; -->}{z}\cdot <!--\; \cdot \; -->R^{-<!--\; -\; -->1}modN=2\cdot <!--\; \cdot \; -->{32}^{-<!--\; -\; -->1}mod11=9$$z={\overline {z}}\cdot R^{-1}{\bmod {N}}=2\cdot 32^{-1}{\bmod {1}}1=9$ 

ПрименениеПравить

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

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

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

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

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

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

Описание методаПравить

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

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

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

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

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

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

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

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

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