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

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

12.12.2021


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

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

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

Пусть требуется вычислить S = x a mod n {displaystyle S=x^{a}{mod {n}}} , где числа x , a , n {displaystyle x,a,n} достаточно большие и пусть модуль может быть разложен на простые делители n = p 1 p 2 . . . p j {displaystyle n=p_{1}p_{2}...p_{j}} . Тогда для быстрого возведения в степень по модулю можно воспользоваться китайской теоремой об остатках и решить систему уравнений (предварительно посчитав вычеты x a ≡ r i ( mod p i ) {displaystyle x^{a}equiv r_{i}{pmod {p_{i}}}} с использованием теоремы Ферма, где i = 1 , 2 , . . . , j {displaystyle i=1,2,...,j} ):

{ x a ≡ r 1 ( mod p 1 ) , 0 ⩽ r 1 < p 1 x a ≡ r 2 ( mod p 2 ) , 0 ⩽ r 2 < p 2 . . . . . . . . . . . . x a ≡ r j ( mod p j ) , 0 ⩽ r j < p j {displaystyle {egin{cases}x^{a}equiv r_{1}{pmod {p_{1}}},qquad 0leqslant r_{1}<p_{1}x^{a}equiv r_{2}{pmod {p_{2}}},qquad 0leqslant r_{2}<p_{2}qquad ......qquad qquad qquad ......x^{a}equiv r_{j}{pmod {p_{j}}},qquad 0leqslant r_{j}<p_{j}end{cases}}}

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

Пример

Пусть требуется вычислить S = 3 5 mod 3 0 {displaystyle S=3^{5}{mod {3}}0}

{ t = 3 5 ≡ 1 ( mod 2 ) t = 3 5 ≡ 0 ( mod 3 ) t = 3 5 ≡ 3 ( mod 5 ) {displaystyle {egin{cases}t=3^{5}equiv 1{pmod {2}}t=3^{5}equiv 0{pmod {3}}t=3^{5}equiv 3{pmod {5}}end{cases}}}

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

{ t = 3 5 = 1 + 2 u t = 3 5 = 0 + 3 v t = 3 5 = 3 + 5 w {displaystyle {egin{cases}t=3^{5}=1+2ut=3^{5}=0+3vt=3^{5}=3+5wend{cases}}}

Подставив t из первого уравнения во второе, получим 1 + 2 u ≡ 0 ( mod 3 ) {displaystyle 1+2uequiv 0{pmod {3}}} , тогда 2 u ≡ 2 ( mod 3 ) {displaystyle 2uequiv 2{pmod {3}}} , или u ≡ 1 ( mod 3 ) {displaystyle uequiv 1{pmod {3}}} , или u = 1 + 3 h {displaystyle u=1+3h} ;

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

тогда t = 3 5 ≡ 1 + 2 ( 1 + 3 ⋅ 0 ) ≡ 3 ( mod 5 ) {displaystyle t=3^{5}equiv 1+2(1+3cdot 0)equiv 3{pmod {5}}} следовательно, S = 3 5 mod 5 = 3 {displaystyle S=3^{5}{mod {5}}=3} ;

Применение

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

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

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

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

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

Пусть требуется вычислить x a mod n {displaystyle x^{a}{mod {n}}} . Представим степень 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=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 ) {displaystyle a_{j}=(0,1)}

Представим x a mod n {displaystyle x^{a}{mod {n}}} в виде:

x a mod n = x a j − 1 2 j − 1 + a j − 2 2 j − 2 + . . . + a 2 2 2 + a 1 2 1 + a 0 mod n = {displaystyle x^{a}{mod {n}}=x^{a_{j-1}2^{j-1}+a_{j-2}2^{j-2}+...+a_{2}2^{2}+a_{1}2^{1}+a_{0}}{mod {n}}=}

= ( x 2 ) a j − 1 2 j − 2 + a j − 2 2 j − 3 + . . . + a 1 2 0 x a 0 mod n = {displaystyle =(x^{2})^{a_{j-1}2^{j-2}+a_{j-2}2^{j-3}+...+a_{1}2^{0}}x^{a_{0}}{mod {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 mod 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}}{mod {n}}=}

= ( . . . ( ( x 2 ) 2 . . . ) 2 ) a j − 1 . . . ( x 8 ) a 3 ( x 4 ) a 2 ( x 2 ) a 1 x a 0 mod n {displaystyle =(...((x^{2})^{2}...)^{2})^{a_{j-1}}...(x^{8})^{a_{3}}(x^{4})^{a_{2}}(x^{2})^{a_{1}}x^{a_{0}}{mod {n}}}

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

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

Пример

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

= ( ( ( ( ( ( ( 249 2 ) 2 ) 2 ) 2 ) 2 ) 2 ) 2 ) 2 ( ( ( ( ( 249 2 ) 2 ) 2 ) 2 ) 2 ) 2 249 mod 4 99 = [ 249 2 ≡ 125 ( mod 4 99 ) ] = {displaystyle =(((((((249^{2})^{2})^{2})^{2})^{2})^{2})^{2})^{2}(((((249^{2})^{2})^{2})^{2})^{2})^{2}249{mod {4}}99=[249^{2}equiv 125({mod {4}}99)]=}

= ( ( ( ( ( ( 125 2 ) 2 ) 2 ) 2 ) 2 ) 2 ) 2 ( ( ( ( 125 2 ) 2 ) 2 ) 2 ) 2 249 mod 4 99 = [ 125 2 ≡ 156 ( mod 4 99 ) ] = {displaystyle =((((((125^{2})^{2})^{2})^{2})^{2})^{2})^{2}((((125^{2})^{2})^{2})^{2})^{2}249{mod {4}}99=[125^{2}equiv 156({mod {4}}99)]=}

= ( ( ( ( ( 156 2 ) 2 ) 2 ) 2 ) 2 ) 2 ( ( ( 156 2 ) 2 ) 2 ) 2 249 mod 4 99 = [ 156 2 ≡ 384 ( mod 4 99 ) ] = {displaystyle =(((((156^{2})^{2})^{2})^{2})^{2})^{2}(((156^{2})^{2})^{2})^{2}249{mod {4}}99=[156^{2}equiv 384({mod {4}}99)]=}

= ( ( ( ( 384 2 ) 2 ) 2 ) 2 ) 2 ( ( 384 2 ) 2 ) 2 249 mod 4 99 = [ 384 2 ≡ 251 ( mod 4 99 ) ] = {displaystyle =((((384^{2})^{2})^{2})^{2})^{2}((384^{2})^{2})^{2}249{mod {4}}99=[384^{2}equiv 251({mod {4}}99)]=}

= ( ( ( 251 2 ) 2 ) 2 ) 2 ( 251 2 ) 2 249 mod 4 99 = [ 251 2 ≡ 127 ( mod 4 99 ) ] = {displaystyle =(((251^{2})^{2})^{2})^{2}(251^{2})^{2}249{mod {4}}99=[251^{2}equiv 127({mod {4}}99)]=}

= ( ( 127 2 ) 2 ) 2 127 2 249 mod 4 99 = [ 127 2 ≡ 161 ( mod 4 99 ) ] = {displaystyle =((127^{2})^{2})^{2}127^{2}249{mod {4}}99=[127^{2}equiv 161({mod {4}}99)]=}

= ( 161 2 ) 2 161 ∗ 249 mod 4 99 = [ 161 2 ≡ 472 ( mod 4 99 ) ] = {displaystyle =(161^{2})^{2}161*249{mod {4}}99=[161^{2}equiv 472({mod {4}}99)]=}

= 472 2 161 ∗ 249 mod 4 99 = [ 472 2 ≡ 230 ( mod 4 99 ) ] = {displaystyle =472^{2}161*249{mod {4}}99=[472^{2}equiv 230({mod {4}}99)]=}

= 230 ∗ 161 ∗ 249 mod 4 99 = 447 {displaystyle =230*161*249{mod {4}}99=447}

Применение

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

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

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

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

История

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

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

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

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

То есть, для наглядности, запишем выражение для возведения x {displaystyle x} в 3 {displaystyle 3} степень: M ( M ( M ( x ¯ , x ¯ ) , x ¯ ) , 1 ) = x 3 mod N {displaystyle M(M(M({overline {x}},{overline {x}}),{overline {x}}),1)=x^{3}{mod {N}}}

В итоге получаем образ x ¯ = x R mod N {displaystyle {overline {x}}=xR{mod {N}}} , от которого мы можем получить конечный результат x = x ¯ R − 1 mod N {displaystyle x={overline {x}}R^{-1}{mod {N}}} , причем выражение R − 1 mod N {displaystyle R^{-1}{mod {N}}} вычислено заранее. Для произведения двух чисел результат будет выглядеть как z = z ¯ R − 1 mod N = x ¯ y ¯ R − 1 mod N ≡ x ¯ y ¯ − ( x ¯ y ¯ ( N − 1 mod R ) mod R ) N R mod N {displaystyle z={overline {z}}R^{-1}{mod {N}}={overline {x}}{overline {y}}R^{-1}{mod {N}}equiv {frac {{overline {x}}{overline {y}}-({overline {x}}{overline {y}}(N^{-1}{mod {R}}){mod {R}})N}{R}}{mod {N}}}

Пример

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

3 {displaystyle 3} имеет образ 3 ⋅ R mod N = 96 mod 1 1 = 8 {displaystyle 3cdot R{mod {N}}=96{mod {1}}1=8}

(для проверки 9 {displaystyle 9} имеет образ 9 ⋅ R mod N = 288 mod 1 1 = 2 {displaystyle 9cdot R{mod {N}}=288{mod {1}}1=2} )

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

w = x ¯ ⋅ x ¯ = 64 {displaystyle w={overline {x}}cdot {overline {x}}=64} ,

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

q = N − 1 mod R = 3 {displaystyle q=N^{-1}{mod {R}}=3} ,

u = − w ⋅ q mod R = − 64 ⋅ 3 mod 3 2 = − 192 mod 3 2 = 0 {displaystyle u=-wcdot q{mod {R}}=-64cdot 3{mod {3}}2=-192{mod {3}}2=0} ,

z ¯ = ( w + u ⋅ N ) / R = ( 64 + 0 ⋅ 32 ) / 32 = 2 {displaystyle {overline {z}}=(w+ucdot N)/R=(64+0cdot 32)/32=2}

Соответственно прообраз z = z ¯ ⋅ R − 1 mod N = 2 ⋅ 32 − 1 mod 1 1 = 9 {displaystyle z={overline {z}}cdot R^{-1}{mod {N}}=2cdot 32^{-1}{mod {1}}1=9}

Применение

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

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

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

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

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

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

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

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

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

Выражения вида a b ( mod n ) {displaystyle a^{b}({mod {n}})} имеет оценку вычислительной сложности — O s ( ( log ⁡ n ) 3 ) {displaystyle O_{s}((log n)^{3})}