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

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

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

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

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

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

 In: an integer x; an integer n
 Out: xn
 
 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 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);
 end function 

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

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

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

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

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

$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 , и тогда желаемым результатом будет левый множитель.

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

  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 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).

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

  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 odd then
        y := x * y;
        n := n - 1;
      x := x * x;
      n := n / 2;
    return x * y

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

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

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

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

Каждое возведение в квадрат приводит примерно к удвоению количества цифр по сравнению с предыдущим, и поэтому, если умножение двух d -значных чисел реализуется за O( d ^к ) операций для некоторого фиксированного 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 ^к . Впервые он был предложен Брауэром в 1939 году. В приведенном ниже алгоритме мы используем следующие функции f (0) = ( k , 0) и f ( m ) = ( s , u ), где m = u · 2 ^с с тобой странно.

Алгоритм:

Вход

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

Выход

Элемент х ^н в 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 должно быть наименьшим целым числом, удовлетворяющим

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

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

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

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

Алгоритм:

Вход

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

Выход

Элемент х ^н G ​ .

Алгоритм:

y := 1; i := l - 1
while i > -1 do
    if ni = 0 then
        y := y2' i := i - 1
    else
        s := max{i - k + 1, 0}
        while ns = 0 do
            s := s + 1
        for h := 1 to i - s + 1 do
            y := y2
        u := (ni, ni-1, ..., ns)2
        y := y * xu
        i := 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. ^н когда основание фиксировано, а показатель степени меняется. Как можно видеть, предварительные вычисления играют ключевую роль в этих алгоритмах.

метод Яо

Метод Яо ортогонален методу 2 ^к -арный метод, в котором показатель степени разлагается по основанию b = 2 ^к и вычисления выполняются так же, как в алгоритме выше. Пусть 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]$.

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

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

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

Этот метод вычисления $x^{n}$ в группе G , где 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}},$

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

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

Begin loop
    Find $M\in [0,l-1]$, such that $\forall i\in [0,l-1],n_{M}\geq n_{i}$.
    Find $N\in {\big (}[0,l-1]-M{\big )}$, such that $\forall i\in {\big (}[0,l-1]-M{\big )},n_{N}\geq n_{i}$.
    Break loop if $n_{N}=0$.
    Let $q=\lfloor n_{M}/n_{N}\rfloor$, and then let $n_{N}=(n_{M}{\bmod {n}}_{N})$.
    Compute recursively $x_{M}^{q}$, and then let $x_{N}=x_{N}\cdot x_{M}^{q}$.
End loop;
Return $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 модульных умножений.

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

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

Мощность( Икс , - п ) = (Сила( Икс , п )) ⁻¹ .

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

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

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

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

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

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

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

$c_{0}=0$
for i = 0 to l − 1 do
  $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}$
return $(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 ), поэтому эти алгоритмы асимптотически улучшаются при возведении в степень за счет возведения в квадрат в лучшем случае только с постоянным коэффициентом.

См. также

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