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

Эта статья может быть запутанной или непонятной для читателей . Пожалуйста, помогите прояснить статью . Об этом идет обсуждение на talk:Exponentiation by squaring § Least significant bit is first . ( Май 2022 ) ( Узнайте, как и когда удалять это сообщение )

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Exponentiation by squaring" – news · newspapers · books · scholar · JSTOR (February 2018) (Learn how and when to remove this message)

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

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

Если показатель степени n равен нулю, то ответ 1. Если показатель степени отрицательный, то мы можем повторно использовать предыдущую формулу, переписав значение с использованием положительного показателя степени. То есть,$${\displaystyle 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 умножений.${\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 := - n ; если n = 0 то вернуть 1 y := 1 ; пока n > 1 сделать если n нечетно то y := x * y ; n := n - 1 ; x := x * x ; n : = n / 2 ; вернуть x * y                                                           

Корректность алгоритма обусловлена ​​тем, что является инвариантным в ходе вычислений: он находится в начале и он находится в конце.${\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 )}.}$

Этот алгоритм вычисляет значение 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 ₀ ) _{2 ^k} и предварительно вычисленные значения .${\displaystyle 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 2 y := y * x u  для j := 1 до s сделать 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 ²⁴ , x ⁴⁸ , x ^{49 , x 98} , x ⁹⁹ , x ¹⁹⁸ , x ¹⁹⁹ , x ³⁹⁸ . Но мы также можем вычислить 1, x ³ , x ⁶ , x 12 ^{, x 24} , 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 .

Алгоритм:

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

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

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

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

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

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

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

Метод Яо ортогонален 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]}$

Пусть x _i = x ^{b _i} .

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

${\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 = ^2k и b _i = h ⁱ , то значения n _i будут просто цифрами n в системе счисления с основанием h . Метод Яо сначала собирает в u те x _i , которые появляются в наивысшей степени ⁠ ⁠${\displaystyle h-1}$ ; в следующем раунде те, которые имеют степень ⁠ ⁠ ,${\displaystyle h-2}$ также собираются в u и т. д. Переменная y умножается ⁠ ⁠${\displaystyle h-1}$ раз на начальную u , ⁠ ⁠${\displaystyle h-2}$ раз на следующие по величине степени и т. д. Алгоритм использует ⁠ ⁠${\displaystyle w+h-2}$ умножения, и ⁠ ⁠${\displaystyle w+1}$ элементы должны быть сохранены для вычисления x ⁿ . ^[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-squared , где "*" интерпретируется как x * y = xy mod 2345 (то есть умножение, за которым следует деление с остатком), приводит всего к 27 умножениям и делениям целых чисел, которые все могут быть сохранены в одном машинном слове. Как правило, любой из этих подходов потребует менее 2log ₂ (722340) ≤ 40 модульных умножений.

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

Мощность( x , − n ) = Мощность( x ⁻¹ , n ) ,

Мощность( x , − n ) = (Мощность( x , n )) ⁻¹ .

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

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

В некоторых вычислениях может быть более эффективно разрешить отрицательные коэффициенты и, следовательно, использовать обратную базу, при условии, что инверсия в G «быстрая» или была предварительно вычислена. Например, при вычислении x ^{2 k −1} бинарный метод требует k −1 умножений и k −1 возведений в квадрат. Однако можно выполнить k возведений в квадрат, чтобы получить x ^{2 k} , а затем умножить на x ^−1, чтобы получить 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, которая удовлетворяет и обозначается как . Например, представление NAF числа 478 равно . Это представление всегда имеет минимальный вес Хэмминга. Простой алгоритм вычисления представления 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 ³ используется повторно).

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

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