Возведение в степень путем возведения в квадрат

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

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

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

Метод основан на наблюдении, что для любого целого числа имеем: $n>0$ $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}}$

Если показатель степени $n$ равен нулю, то ответ 1. Если показатель степени отрицательный, то мы можем повторно использовать предыдущую формулу, переписав значение с использованием положительного показателя степени. То есть, $x^{n}=\left({\frac {1}{x}}\right)^{-n}\,.$

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

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

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

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

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

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

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

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 := - n ; если n = 0 то вернуть 1 y := 1 ; пока n > 1 сделать если n нечетно то y := x * y ; n := n - 1 ; x := x * x ; n : = n / 2 ; вернуть x * y

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

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

Сложность вычислений

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

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

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

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

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

Алгоритм:

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

Выход: Элемент x ⁿ в G

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

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

\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 ²⁴ , x ⁴⁸ , x ^{49 , x}⁹⁸ , x ⁹⁹ , x ¹⁹⁸ , x ¹⁹⁹ , x ³⁹⁸ . Но мы также можем вычислить 1, x ³ , x ⁶ , x 12 ^{, x}²⁴ , x ⁴⁸ , x ⁹⁶ , x ¹⁹² , x ¹⁹⁹ , x ³⁹⁸ , что экономит одно умножение и равносильно оценке (110 001 110) ₂

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

Алгоритм:

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

Выход: Элемент x ⁿ ∈ G .

Алгоритм:

y := 1; i := l - 1 пока i > -1 сделать  если n _i = 0 тогда y := y ² ' i := i - 1 иначе с := макс{i - k + 1, 0} в то время как n _s = 0 do s := s + 1 ^{[примечания 1]} для h := 1 to i - s + 1 do y := y ² u := (ni _, n _i-1 , ..., n _s ) ₂ y := y * x ^u я := с - 1вернуть y

Лестничный метод Монтгомери

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

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

x ₁ = x; x ₂ = x ²для i = k - 2 до 0 сделать  если n _i = 0 тогда x ₂ = x ₁ * x ₂ ; x ₁ = x ₁² иначе x ₁ = x ₁ * x ₂ ; x ₂ = x ₂²вернуть x ₁

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

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

Показатель степени с фиксированным основанием

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

Метод Яо

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

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

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

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

Пусть $x i = x b i$ .

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

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 0 ... x b w -1$ , элемент $x n$ вычисляется с использованием следующего алгоритма:

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 = 2k$ и $b i = h i$ , то значения $n i$ будут просто цифрами $n$ в системе счисления с основанием $h$ . Метод Яо сначала собирает в u те $x i$ , которые появляются в наивысшей степени ⁠ ⁠ $h-1$ ; в следующем раунде те, которые имеют степень ⁠ ⁠ , $h-2$ также собираются в $u$ и т. д. Переменная y умножается ⁠ ⁠ $h-1$ раз на начальную $u$ , ⁠ ⁠ $h-2$ раз на следующие по величине степени и т. д. Алгоритм использует ⁠ ⁠ $w+h-2$ умножения, и ⁠ ⁠ $w+1$ элементы должны быть сохранены для вычисления $x n$ . ^[1]

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

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

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

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$ $1$ на $n$ $0$ используется для возврата частного $q$ и остатка $n$ $1$ $mod$ $n$ $0$ . $q=\left\lfloor {\frac {n_{1}}{n_{0}}}\right\rfloor$

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

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

13789722341 (мод. 2345) = 2029

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

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

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

Мощность(x, - n) = Мощность(x -1, n)

Мощность(x, - n) = (Мощность(x, n)) -1

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

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

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

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

Для этого мы определяем знаковое цифровое представление целого числа $n$ в системе счисления с основанием $b$ как

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

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

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

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

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

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

x^{15}=x\times (x\times [x\times x^{2}]^{2})^{2}

(возведение в квадрат, умножение на 6),

x^{15}=x^{3}\times ([x^{3}]^{2})^{2}

(оптимальная цепочка сложения, 5 умножается, если x ³ используется повторно).

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

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

Примечания

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

Ссылки

^ ab Cohen, H.; Frey, G., ред. (2006). Справочник по эллиптической и гиперэллиптической криптографии . Дискретная математика и ее приложения. Chapman & Hall/CRC. ISBN 9781584885184.
^ Монтгомери, Питер Л. (1987). «Ускорение методов Полларда и эллиптической кривой факторизации» (PDF) . Math. Comput . 48 (177): 243–264. doi : 10.1090/S0025-5718-1987-0866113-7 .
^ Gueron, Shay (5 апреля 2012 г.). "Эффективные программные реализации модульного возведения в степень" (PDF) . Journal of Cryptographic Engineering . 2 (1): 31–43. doi :10.1007/s13389-012-0031-5. S2CID 7629541.