Возведение в степень возведением в степень

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

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

Основной метод

Рекурсивная версия

Метод основан на наблюдении, что для любого целого числа имеет место: ${\displaystyle n>0}$

$${\displaystyle x^{n}={\begin{cases}x\,(x^{2})^{(n-1)/2},&{\mbox{if }}n{\mbox{ is odd}}\\(x^{2})^{n/2},&{\mbox{if }}n{\mbox{ is even}}\end{cases}}}$$

Если показатель степени равен нулю, то ответ равен 1, а если показатель степени отрицательный, мы можем повторно использовать предыдущую формулу, переписав значение, используя положительный показатель степени. То есть,

$${\displaystyle x^{-n}=\left({\frac {1}{x}}\right)^{n}\,.}$$

Вместе они могут быть реализованы непосредственно как следующий рекурсивный алгоритм :

In: целое число x; целое число n Вышел: х н  exp_by_squaring(x, n) если n < 0, то return exp_by_squaring(1 / x, -n); иначе, если n = 0, то возврат 1; иначе, если n четно, то return exp_by_squaring(x * x, n/2); иначе, если n нечетное, то return x * exp_by_squaring(x * x, (n - 1)/2); конечная функция

При каждом рекурсивном вызове младшие цифры двоичного представления числа n удаляются. Отсюда следует, что количество рекурсивных вызовов равно количеству бит двоичного представления n . Таким образом, этот алгоритм вычисляет это количество квадратов и меньшее количество умножений, которое равно числу 1 в двоичном представлении n . Это логарифмическое количество операций необходимо сравнить с тривиальным алгоритмом, требующим n - 1 умножений. ${\displaystyle \lceil \log _{2}n\rceil ,}$

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

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

С постоянной вспомогательной памятью

Варианты, описанные в этом разделе, основаны на формуле

${\displaystyle yx^{n}={\begin{cases}(yx)\,(x^{2})^{(n-1)/2},&{\mbox{if }}n{\mbox{ is odd}}\\y\,(x^{2})^{n/2},&{\mbox{if }}n{\mbox{ is even}}.\end{cases}}}$

Если применить эту формулу рекурсивно, начав с y = 1 , в конечном итоге получим показатель степени, равный 0 , и тогда желаемым результатом будет левый множитель.

Это может быть реализовано как функция хвостовой рекурсии:

 Функция exp_by_squaring ( x , n ) возвращает exp_by_squaring2 ( 1 , x , n ) Функция exp_by_squaring2 ( y , x , n ) если n < 0 , то возвращает exp_by_squaring2 ( y , 1 / x , -n ) ; иначе , если n = 0 , вернуть y ; иначе , если n четно , верните exp_by_squaring2 ( y , x * x , n / 2 ) ; иначе , если n нечетно , верните exp_by_squaring2 ( x * y , x * x , ( n - 1 ) / 2 ) .                                                             

Итерационная версия алгоритма также использует ограниченное вспомогательное пространство и имеет вид

 Функция exp_by_squaring_iterative ( x , n ) , если n < 0 , то x := 1 / x ; п := - п ; если n = 0 , то вернуть 1 y := 1 ; в то время как n > 1 , если n нечетно, то y : = x * y ; п := п - 1 ; х := х * х ; п := п / 2 ; вернуть х * у                                                           

Корректность алгоритма обусловлена ​​тем, что он инвариантен во время вычислений; это в начале; и это в конце. ${\displaystyle yx^{n}}$ ${\displaystyle 1\cdot x^{n}=x^{n}}$ ${\displaystyle yx^{1}=xy}$

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

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

Краткий анализ показывает, что такой алгоритм использует возведение в квадрат и не более чем умножение, где обозначает функцию пола . Точнее, количество умножений на единицу меньше , чем количество единиц, присутствующих в двоичном представлении n . Для n больше примерно 4 это в вычислительном отношении более эффективно, чем наивное многократное умножение основания само на себя. ${\displaystyle \lfloor \log _{2}n\rfloor }$ ${\displaystyle \lfloor \log _{2}n\rfloor }$ ${\displaystyle \lfloor \;\rfloor }$

Каждое возведение в квадрат приводит примерно к удвоению количества цифр по сравнению с предыдущим, и поэтому, если умножение двух d -значных чисел реализуется за O( d ^k ) операций для некоторого фиксированного k , то сложность вычисления x ⁿ определяется выражением

${\displaystyle \sum \limits _{i=0}^{O(\log n)}{\big (}2^{i}O(\log x){\big )}^{k}=O{\big (}(n\log x)^{k}{\big )}.}$

2 k -арный метод

Этот алгоритм вычисляет значение x ⁿ после расширения показателя степени по основанию 2 ^k . Впервые он был предложен Брауэром в 1939 году. В приведенном ниже алгоритме мы используем следующие функции f (0) = ( k , 0) и f ( m ) = ( s ,  u ), где m = u · 2 ^s с ты странный.

Алгоритм:

Вход

Элемент x из G , параметр k > 0, неотрицательное целое число n = ( n _{l −1} , n _{l −2} , ..., n ₀ ) _{2 ^k} и заранее вычисленные значения . ${\displaystyle x^{3},x^{5},...,x^{2^{k}-1}}$

Выход

Элемент x ⁿ в G

у := 1; i := l - 1 , пока i ≥ 0, делать (s, u) := f(n i ) for j := 1 до k - s do y := y 2 y := y * x u  for j := 1 до s do y := y 2 я := я - 1вернуть y

Для оптимальной эффективности k должно быть наименьшим целым числом, удовлетворяющим ^[1]

${\displaystyle \lg n<{\frac {k(k+1)\cdot 2^{2k}}{2^{k+1}-k-2}}+1.}$

Метод скользящего окна

Этот метод является эффективным вариантом 2 ^k -арного метода. Например, чтобы вычислить показатель степени 398, который имеет двоичное разложение (110 001 110) ₂ , мы берем окно длиной 3 с помощью алгоритма 2 ^k -арного метода и вычисляем 1, x ³ , x ⁶ , x ¹² , x ²⁴ , х ⁴⁸ , х ⁴⁹ , х ⁹⁸ , х ⁹⁹ , х ¹⁹⁸ , х ¹⁹⁹ , х ³⁹⁸ . Но мы также можем вычислить 1, x ³ , x ⁶ , x ¹² , x ²⁴ , x ⁴⁸ , x ⁹⁶ , x ¹⁹² , x ¹⁹⁹ , x ³⁹⁸ , что экономит одно умножение и эквивалентно вычислению (110 001 110) ₂

Вот общий алгоритм:

Алгоритм:

Вход

Элемент x из G , неотрицательное целое число n =( n _{l −1} , n _{l −2} , ..., n ₀ ) ₂ , параметр k > 0 и предварительно вычисленные значения . ${\displaystyle x^{3},x^{5},...,x^{2^{k}-1}}$

Выход

Элемент x ⁿ ∈ G .

Алгоритм:

у := 1; i := l - 1 while i > -1 делать  if n i = 0 then y := y 2 ' i := i - 1 else s := max{i - k + 1, 0} в то время как n s = 0 do s := s + 1 [примечания 1]  для h := 1 до i - s + 1 do y := y 2 u := (n i , n i-1 , ..., n s ) 2 y := y * x u я := с - 1вернуть y

Лестничная техника Монтгомери

Многие алгоритмы возведения в степень не обеспечивают защиту от атак по побочным каналам . А именно, злоумышленник, наблюдающий за последовательностью возведения в квадрат и умножения, может (частично) восстановить показатель степени, участвующий в вычислении. Это проблема, если показатель степени должен оставаться секретным, как во многих криптосистемах с открытым ключом . Эта проблема решается с помощью метода, называемого « лестница Монтгомери » ^{[2] .}

Учитывая двоичное разложение положительного, ненулевого целого числа n = ( n _{k −1} ... n ₀ ) ₂ с n _k−1 = 1, мы можем вычислить x ⁿ следующим образом:

х 1 = х; x 2 = x 2 для i = k - 2 до 0 сделать  , если n i = 0 , то x 2 = x 1 * x 2 ; Икс 1 = Икс 1 2  еще Икс 1 = Икс 1 * Икс 2 ; х 2 = х 2 2 вернуть х 1

Алгоритм выполняет фиксированную последовательность операций ( до log  n ): умножение и возведение в квадрат происходит для каждого бита экспоненты, независимо от конкретного значения бита. Аналогичный алгоритм умножения на удвоение существует.

Эта конкретная реализация лестницы Монтгомери еще не защищена от атак по времени кэширования : злоумышленник все еще может наблюдать задержки доступа к памяти, поскольку доступ к различным переменным осуществляется в зависимости от значения битов секретного показателя степени. Современные криптографические реализации используют технику «разброса», чтобы гарантировать, что процессор всегда пропускает более быстрый кэш. ^[3]

Экспонента с фиксированной базой

Существует несколько методов, которые можно использовать для вычисления x ⁿ , когда основание фиксировано, а показатель степени меняется. Как можно видеть, предварительные вычисления играют ключевую роль в этих алгоритмах.

метод Яо

Метод Яо ортогонален 2 ^k -арному методу, где показатель степени разлагается по основанию b = 2 ^k , а вычисления выполняются так же, как в алгоритме выше. Пусть n , n _i , b и b _i — целые числа.

Пусть показатель степени n запишется как

${\displaystyle n=\sum _{i=0}^{w-1}n_{i}b_{i},}$

где для всех . ${\displaystyle 0\leqslant n_{i}<h}$ ${\displaystyle i\in [0,w-1]}$

Пусть Икс _я = Икс ^{б _я} .

Тогда алгоритм использует равенство

${\displaystyle x^{n}=\prod _{i=0}^{w-1}x_{i}^{n_{i}}=\prod _{j=1}^{h-1}{\bigg [}\prod _{n_{i}=j}x_{i}{\bigg ]}^{j}.}$

Учитывая элемент x из G и показатель степени n , записанный в приведенной выше форме, а также заранее вычисленные значения x ^{b ₀} ... x ^{b _{w −1}} , элемент x ⁿ вычисляется с использованием приведенного ниже алгоритма:

y = 1, u = 1, j = h - 1, в то время как j > 0 делать  для i = 0 до w - 1 делать  , если n i = j , то u = u × x b i у = у × ты j = j - 1вернуть y

Если мы установим h = 2 ^k и b _i = h ⁱ , то значения n _i будут просто цифрами n по основанию h . Метод Яо собирает в u сначала те xi _, которые кажутся наивысшей степени ; в следующем раунде те, у кого есть мощность, также собираются в u и т. д. Переменная y умножается на начальную u , на следующую по величине степень и так далее. Алгоритм использует умножение, и элементы должны быть сохранены для вычисления x ⁿ . ^[1] ${\displaystyle h-1}$ ${\displaystyle h-2}$ ${\displaystyle h-1}$ ${\displaystyle h-2}$ ${\displaystyle w+h-2}$ ${\displaystyle w+1}$

Евклидов метод

Евклидов метод был впервые представлен в книге «Эффективное возведение в степень с использованием предварительных вычислений и цепочек сложения векторов» П.Д. Руиджа.

Этот метод вычислений в группе G , где n — натуральное целое число, алгоритм которого приведен ниже, рекурсивно использует следующее равенство: ${\displaystyle x^{n}}$

${\displaystyle x_{0}^{n_{0}}\cdot x_{1}^{n_{1}}=\left(x_{0}\cdot x_{1}^{q}\right)^{n_{0}}\cdot x_{1}^{n_{1}\mod n_{0}},}$

где . Другими словами, евклидово деление показателя n ₁ на n ₀ используется для получения частного q и остатка n ₁ mod n ₀ . ${\displaystyle q=\left\lfloor {\frac {n_{1}}{n_{0}}}\right\rfloor }$

Учитывая базовый элемент x в группе G и показатель степени , записанный как в методе Яо, элемент рассчитывается с использованием заранее вычисленных значений , а затем алгоритма, приведенного ниже. ${\displaystyle n}$ ${\displaystyle x^{n}}$ ${\displaystyle l}$ ${\displaystyle x^{b_{0}},...,x^{b_{l_{i}}}}$

Начать цикл  Найти ,  ${\displaystyle M\in [0,l-1]}$ такой, что .  ${\displaystyle \forall i\in [0,l-1],n_{M}\geq n_{i}}$ Найдите ,  ${\displaystyle N\in {\big (}[0,l-1]-M{\big )}}$ такой, что .  ${\displaystyle \forall i\in {\big (}[0,l-1]-M{\big )},n_{N}\geq n_{i}}$ Разорвите цикл,  если .  ${\displaystyle n_{N}=0}$ Пусть ,  ${\displaystyle q=\lfloor n_{M}/n_{N}\rfloor }$ и тогда пусть .  ${\displaystyle n_{N}=(n_{M}{\bmod {n}}_{N})}$ Вычислите рекурсивно ,  ${\displaystyle x_{M}^{q}}$ а затем позвольте .  ${\displaystyle x_{N}=x_{N}\cdot x_{M}^{q}}$Конец цикла ;Возвращаться . ${\displaystyle x^{n}=x_{M}^{n_{M}}}$

Алгоритм сначала находит наибольшее значение среди n _i , а затем верхнюю границу в наборе { n _i \ i ≠ M } . Затем он возводит x _M в степень q , умножает это значение на x _N , а затем присваивает x _N результат этого вычисления и n _M значение n _M по модулю n _N.

Дальнейшие применения

Этот подход также работает с полугруппами , которые не имеют нулевой характеристики , например, позволяя быстро вычислять большие показатели степени по модулю числа. Особенно в криптографии полезно вычислять степени в кольце целых чисел по модулю q . Например, оценка

13789 ⁷²²³⁴¹ (мод. 2345) = 2029

потребовалось бы очень много времени и много места для хранения, если бы использовался простой метод вычисления 13789 ⁷²²³⁴¹ и последующего получения остатка при делении на 2345. Даже использование более эффективного метода займет много времени: возведите в квадрат 13789, возьмите остаток от деления на 2345, умножьте результат на 13789 и так далее.

Применение описанного выше алгоритма exp-by-square , где "*" интерпретируется как x * y = xy mod 2345 (то есть умножение, за которым следует деление с остатком), приводит только к 27 умножениям и делениям целых чисел, которые все могут быть сохранены. в одном машинном слове. Как правило, любой из этих подходов требует менее 2log ₂ (722340) ≤ 40 модульных умножений.

Этот подход также можно использовать для вычисления целочисленных степеней в группе , используя любое из правил:

Мощность( Икс , - п ) = Мощность ( Икс ^-1 , п ) ,

Мощность( Икс , - п ) = ( Мощность ( Икс , п )) ^-1 .

Этот подход также работает в некоммутативных полугруппах и часто используется для вычисления степеней матриц .

В более общем смысле, этот подход работает с положительными целочисленными показателями в каждой магме , для которой бинарная операция является степенно-ассоциативной .

Перекодирование знаковых цифр

В некоторых вычислениях может быть более эффективно разрешить отрицательные коэффициенты и, следовательно, использовать обратную базу, при условии, что инверсия в G является «быстрой» или была предварительно вычислена. Например, при вычислении x ^{2 k -1} бинарный метод требует k -1 умножений и k -1 возведения в квадрат. Однако можно выполнить k возведений в квадрат, чтобы получить x ^{2 k} , а затем умножить на x ⁻¹ и получить x ^{2 k −1} .

С этой целью мы определяем знаковое представление целого числа n в системе счисления b как

${\displaystyle n=\sum _{i=0}^{l-1}n_{i}b^{i}{\text{ with }}|n_{i}|<b.}$

Знаковое двоичное представление соответствует конкретному выбору b = 2 и . Это обозначается . Существует несколько методов вычисления этого представления. Представление не уникально. Например, возьмем n = 478 : два различных знаково-двоичных представления задаются как и , где используется для обозначения −1 . Поскольку бинарный метод вычисляет умножение для каждой ненулевой записи в представлении n по основанию 2 , мы заинтересованы в поиске знаково-двоичного представления с наименьшим количеством ненулевых записей, то есть с минимальным числом Хэмминга . масса . Один из способов сделать это — вычислить представление в несмежной форме , или сокращенно NAF, которое удовлетворяет условиям и обозначается . Например, представление числа 478 в NAF равно . Это представление всегда имеет минимальный вес Хэмминга. Простой алгоритм вычисления представления NAF заданного целого числа следующий : ${\displaystyle n_{i}\in \{-1,0,1\}}$ ${\displaystyle (n_{l-1}\dots n_{0})_{s}}$ ${\displaystyle (10{\bar {1}}1100{\bar {1}}10)_{s}}$ ${\displaystyle (100{\bar {1}}1000{\bar {1}}0)_{s}}$ ${\displaystyle {\bar {1}}}$ ${\displaystyle n_{i}n_{i+1}=0{\text{ for all }}i\geqslant 0}$ ${\displaystyle (n_{l-1}\dots n_{0})_{\text{NAF}}}$ ${\displaystyle (1000{\bar {1}}000{\bar {1}}0)_{\text{NAF}}}$ ${\displaystyle n=(n_{l}n_{l-1}\dots n_{0})_{2}}$ ${\displaystyle n_{l}=n_{l-1}=0}$

 ${\displaystyle c_{0}=0}$для i = 0 до l - 1 верните  ${\displaystyle c_{i+1}=\left\lfloor {\frac {1}{2}}(c_{i}+n_{i}+n_{i+1})\right\rfloor }$  ${\displaystyle n_{i}'=c_{i}+n_{i}-2c_{i+1}}$ ${\displaystyle (n_{l-1}'\dots n_{0}')_{\text{NAF}}}$

Другой алгоритм Коямы и Цуруока не требует условия, что ; он по-прежнему минимизирует вес Хэмминга. ${\displaystyle n_{i}=n_{i+1}=0}$

Альтернативы и обобщения

Возведение в степень путем возведения в степень можно рассматривать как неоптимальный алгоритм возведения в степень с помощью цепочки сложения : он вычисляет показатель с помощью цепочки сложения , состоящей из повторяющихся удвоений показателя (возведения в квадрат) и/или увеличения показателя степени только на единицу (умножения на x ). В более общем смысле, если кто-то позволяет суммировать любые ранее вычисленные показатели степени (путем умножения этих степеней x ), иногда можно выполнить возведение в степень, используя меньшее количество умножений (но обычно используя больше памяти). Наименьшая степень, при которой это происходит, соответствует n = 15:

${\displaystyle x^{15}=x\times (x\times [x\times x^{2}]^{2})^{2}}$ (возведение в квадрат, 6 умножений),

${\displaystyle x^{15}=x^{3}\times ([x^{3}]^{2})^{2}}$ (оптимальная цепочка сложения, 5 умножается, если повторно используется x ^{3 ).}

В общем, поиск оптимальной цепочки сложения для заданного показателя степени является сложной задачей, для которой не известны эффективные алгоритмы, поэтому оптимальные цепочки обычно используются только для малых показателей степени (например, в компиляторах , где цепочки для малых степеней предварительно сведены в таблицы). ). Однако существует ряд эвристических алгоритмов, которые, хотя и не являются оптимальными, имеют меньше умножений, чем возведение в степень путем возведения в квадрат, за счет дополнительной бухгалтерской работы и использования памяти. Несмотря на это, количество умножений никогда не растет медленнее, чем Θ (log n ), поэтому эти алгоритмы асимптотически улучшаются при возведении в степень за счет возведения в квадрат в лучшем случае только с постоянным коэффициентом.

Смотрите также

• Модульное возведение в степень
• Векториальная цепочка сложения
• Сокращение Монтгомери
• Несмежная форма
• Дополнительная цепочка

Примечания

1. В этой строке цикл находит самую длинную строку длиной меньше или равной k , оканчивающуюся ненулевым значением. Не все нечетные степени двойки должны быть вычислены, и необходимо учитывать только те, которые конкретно участвуют в вычислении. ${\displaystyle x^{2^{k}-1}}$

Рекомендации

1. Коэн, Х.; Фрей, Г., ред. (2006). Справочник по криптографии эллиптических и гиперэллиптических кривых . Дискретная математика и ее приложения. Чепмен и Холл/CRC. ISBN 9781584885184.
2. Монтгомери, Питер Л. (1987). «Ускорение методов факторизации Полларда и эллиптических кривых» (PDF) . Математика. Вычислить . 48 (177): 243–264. doi : 10.1090/S0025-5718-1987-0866113-7 .
3. Герон, Шей (5 апреля 2012 г.). «Эффективная программная реализация модульного возведения в степень» (PDF) . Журнал криптографической инженерии . 2 (1): 31–43. дои : 10.1007/s13389-012-0031-5. S2CID  7629541.