Возведение в степень возведением в квадрат - Exponentiation by squaring

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

Базовый метод

Метод основан на наблюдении, что для положительного целого n мы имеем

${\ displaystyle x ^ {n} = {\ begin {case} x \, (x ^ {2}) ^ {\ frac {n-1} {2}}, & {\ mbox {if}} n {\ mbox {нечетно}} \\ (x ^ {2}) ^ {\ frac {n} {2}}, & {\ mbox {if}} n {\ mbox {четно}}. \ end {cases} }}$

Пример: . 13 нечетно, поэтому согласно вышеизложенному = . ${\ displaystyle x ^ {13}}$${\ displaystyle x ^ {13}}$${\ Displaystyle х ((х ^ {2}) ^ {6})}$

Можно записать как произведение показателей в виде 2 ^к , для которых 2 ^к <13. = некоторый продукт , , , . Поскольку двоичное представление числа 13 равно 1101, ${\ displaystyle x ^ {13}}$${\ displaystyle x ^ {13}}$${\ displaystyle x ^ {8}}$${\ displaystyle x ^ {4}}$${\ displaystyle x ^ {2}}$${\ displaystyle x ^ {1}}$

${\ displaystyle x ^ {13}}$ знак равно ${\ Displaystyle (х ^ {8}) ^ {1} \ cdot (х ^ {4}) ^ {1} \ cdot (x ^ {2}) ^ {0} \ cdot (x ^ {1}) ^ {1}}$

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

В этом примере показано, как выполнять вычисления с использованием этого метода. Показатель степени 13 равен 1101 в двоичной системе счисления. Биты используются в порядке слева направо. У экспоненты 4 бита, поэтому есть 4 итерации. ${\ displaystyle x ^ {13}}$

Во- первых, инициализировать результат 1: . ${\ Displaystyle г \ leftarrow 1 \, (= х ^ {0})}$

Шаг 1) ; бит 1 = 1, поэтому вычислить ;${\ Displaystyle г \ leftarrow г ^ {2} \, (= х ^ {0})}$${\ Displaystyle г \ leftarrow г \ CDOT х \, (= х ^ {1})}$

Шаг 2) ; бит 2 = 1, поэтому вычислить ;${\ Displaystyle г \ leftarrow г ^ {2} \, (= х ^ {2})}$${\ Displaystyle г \ leftarrow г \ CDOT х \, (= х ^ {3})}$

Шаг 3) ; бит 3 = 0, поэтому мы закончили этот шаг (эквивалентно, это соответствует );${\ Displaystyle г \ leftarrow г ^ {2} \, (= х ^ {6})}$${\ Displaystyle г \ leftarrow г \ CDOT х ^ {0} \, (= х ^ {6})}$

Шаг 4) ; бит 4 = 1, поэтому вычислим .${\ Displaystyle г \ leftarrow г ^ {2} \, (= х ^ {12})}$${\ Displaystyle г \ leftarrow г \ CDOT х \, (= х ^ {13})}$

Если мы запишем в двоичном формате as , это эквивалентно определению последовательности путем разрешения и последующего определения for , где будет равно . ${\ displaystyle n}$${\ displaystyle b_ {k} \ cdots b_ {0}}$${\ displaystyle r_ {k + 1}, \ ldots, r_ {0}}$${\ displaystyle r_ {k + 1} = 1}$${\ displaystyle r_ {i} = r_ {i + 1} ^ {2} x ^ {b_ {i}}}$${\ Displaystyle я = к, \ ldots, 0}$${\ displaystyle r_ {0}}$${\ Displaystyle х ^ {п}}$

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

  Function exp_by_squaring(x, n)
    if n < 0  then return exp_by_squaring(1 / x, -n);
    else if n = 0  then return  1;
    else if n = 1  then return  x ;
    else if n is even  then return exp_by_squaring(x * x,  n / 2);
    else if n is odd  then return x * exp_by_squaring(x * x, (n - 1) / 2);

Хотя этот алгоритм не является хвостовым рекурсивным , его можно переписать в хвостовой рекурсивный алгоритм, введя вспомогательную функцию:

  Function exp_by_squaring(x, n)
    return exp_by_squaring2(1, x, n)
  Function exp_by_squaring2(y, x, n)
    if n < 0  then return exp_by_squaring2(y, 1 / x, - n);
    else if n = 0  then return  y;
    else if n = 1  then return  x * y;
    else if n is even  then return exp_by_squaring2(y, x * x,  n / 2);
    else if n is odd  then return exp_by_squaring2(x * y, x * x, (n - 1) / 2).

Вариант с хвостовой рекурсией также может быть построен с использованием пары аккумуляторов вместо вспомогательной функции, как показано в примере F # ниже. Накопители a1 и a2 можно рассматривать как хранящие значения, и где i и j инициализируются значениями 1 и 0 соответственно. В четном случае i удваивается, а в нечетном случае j увеличивается на i. Конечный результат - где . ${\ Displaystyle х ^ {я}}$${\ displaystyle x ^ {j}}$${\ Displaystyle х ^ {я + j}}$${\ Displaystyle я + J = п}$

let exp_by_squaring x n =
    let rec _exp x n' a1 a2 =
        if   n' = 0   then 1
        elif n' = 1   then a1*a2
        elif n'%2 = 0 then _exp x (n'/2) (a1*a1) a2
        else               _exp x (n'-1) a1 (a1*a2)
    _exp x n x 1

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

  Function exp_by_squaring_iterative(x, n)
    if n < 0 then
      x := 1 / x;
      n := -n;
    if n = 0 then return 1
    y := 1;
    while n > 1 do
      if n is even then 
        x := x * x;
        n := n / 2;
      else
        y := x * y;
        x := x * x;
        n := (n - 1) / 2;
    return x * y

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

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

Этот алгоритм вычисляет значение 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

y := 1; i := l - 1
while i ≥ 0 do
    (s, u) := f(ni)
    for j := 1 to k - s do
        y := y2 
    y := y * xu
    for j := 1 to s do
        y := y2
    i := i - 1
return y

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

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

Выход

Элемент х ^п ∈ G .

Алгоритм:

y := 1; i := l - 1
while i > -1 do
    if ni = 0 then
        yy:= y2' i := i - 1
    else
        ss:= max{i - k + 1, 0}
        while ns = 0 do
            ss:= s + 1
        for h := 1 to i - s + 1 do
            yy:= y2
        uu:= (ni, ni-1, ..., ns)2
        yy:= y * xu
        ii:= s - 1
return y

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

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

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

x1 = x; x2 = x2
for i = k - 2 to 0 do
    If ni = 0 then
        x2 = x1 * x2; x1 = x12
    else
        x1 = x1 * x2; x2 = x22
return x1

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

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

Показатель с фиксированной базой

Существует несколько методов, которые можно использовать для вычисления 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
while j > 0 do
    for i = 0 to w - 1 do
        if ni = j then
            u = u × xbi
    y = y × u
    j = j - 1
return y

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

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

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

В этом методе вычислений в группе G , где n - натуральное целое число, алгоритм которого приведен ниже, рекурсивно используется следующее равенство: ${\ Displaystyle х ^ {п}}$

${\ 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 _{1 по} модулю n ₀ . ${\ displaystyle q = \ left \ lfloor {\ frac {n_ {1}} {n_ {0}}} \ right \ rfloor}$

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

Begin loop   
    Find ${\displaystyle M\in [0,l-1]}$, such that ${\displaystyle \forall i\in [0,l-1],n_{M}\geq n_{i}}$.
    Find ${\displaystyle N\in {\big (}[0,l-1]-M{\big )}}$, such that ${\displaystyle \forall i\in {\big (}[0,l-1]-M{\big )},n_{N}\geq n_{i}}$.
    Break loop if ${\displaystyle n_{N}=0}$.
    Let ${\displaystyle q=\lfloor n_{M}/n_{N}\rfloor }$, and then let ${\displaystyle n_{N}=(n_{M}{\bmod {n}}_{N})}$.
    Compute recursively ${\displaystyle x_{M}^{q}}$, and then let ${\displaystyle x_{N}=x_{N}\cdot x_{M}^{q}}$.
End loop;
Return ${\displaystyle x^{n}=x_{M}^{n_{M}}}$.

Алгоритм сначала находит наибольшее значение среди n _i, а затем супремум в наборе { n _i \ i ≠ M } . Тогда он поднимает е _М к источнику д , умножает это значение с й _N , а затем присваивает й г _N результата этого вычисления и п _М значения п _М по модулю п _Н .

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

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

Степень ( x , - n ) = (Мощность ( x , n )) ⁻¹ .

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

Например, оценка

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

потребовалось бы очень много времени и много места для хранения, если бы использовался простой метод: вычислите 13789 ⁷²²³⁴¹ , затем возьмите остаток при делении на 2345. Даже использование более эффективного метода займет много времени: возведите 13789 в квадрат, возьмите остаток при делении на 2345, умножьте результат на 13789 и так далее. Это займет меньше, чем модульное умножение. ${\ Displaystyle 2 \ журнал _ {2} (722340) \ leq 40}$

Применение приведенного выше алгоритма возведения в квадрат с "*", интерпретируемым как x  *  y = xy mod 2345 (то есть умножение с последующим делением на остаток) приводит только к 27 умножениям и делениям целых чисел, которые все могут быть сохранены одним машинным словом.

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

В некоторых вычислениях может быть более эффективным разрешить отрицательные коэффициенты и, следовательно, использовать инверсию основания, при условии, что инверсия в 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 (п_ {l-1} \ точки п_ {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 {для всех}} i \ geqslant 0}$${\ displaystyle (n_ {l-1} \ dots n_ {0}) _ {\ text {NAF}}}$${\ displaystyle (1000 {\ bar {1}} 000 {\ bar {1}} 0) _ {\ text {NAF}}}$${\ Displaystyle п = (п_ {l} п_ {l-1} \ точки n_ {0}) _ {2}}$${\ displaystyle n_ {l} = n_ {l-1} = 0}$

${\displaystyle c_{0}=0}$
for i = 0 to l − 1 do
  ${\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}}$
return ${\displaystyle (n_{l-1}'\dots n_{0}')_{\text{NAF}}}$

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

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

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

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

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

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

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

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

Примечания

использованная литература