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

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

Основной метод [ править ]

Рекурсивная версия [ править ]

Метод основан на наблюдении, что для любого целого числа $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: целое число 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$ удаляются. Отсюда следует, что количество рекурсивных вызовов равно $\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$ , и тогда желаемым результатом будет левый множитель.

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

  Функция   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  ; 
      вернуть   х   *   у

Корректность алгоритма обусловлена тем, что $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 0) 2 к$ и предварительно вычисленные значения $x^{3},x^{5},...,x^{2^{k}-1}$ .

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

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

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

\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 0) 2$ , параметр k > 0 и заранее вычисленные значения $x^{3},x^{5},...,x^{2^{k}-1}$ .

Выход: Элемент х ^н G .

Алгоритм:

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

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

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

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

х ₁ = х;   х ₂ = х ²
для  i = k - 2 до 0  сделать 
     , если  n _i = 0  , то 
          Икс ₂ = Икс ₁ * Икс ₂ ;   х ₁ = х ₁²
    еще 
          Икс ₁ = Икс ₁ * Икс ₂ ;   х ₂ = х ₂²
возврат  х ₁

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

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

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

Существует несколько методов, которые можно использовать для расчета 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 б 0 ... Икс б ш -1$ , элемент $x н$ рассчитывается по приведенному ниже алгоритму:

у = 1, и = 1, j = ч - 1 
  в то время как  j > 0  делать 
     для  i = 0  до  w - 1  делать 
         , если  n _i = j  , то 
              ты = ты × х ^су = у × ты 
      j = j - 1 
  вернуть  y

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

Евклидов метод [ править ]

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

Этот метод вычисления $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 1$ на $n 0$ используется для возврата частного $q$ и остатка $n 1 mod n 0$ .

Учитывая базовый элемент $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-square алгоритма $, где "*" интерпретируется как x * y = xy mod 2345$ (то есть умножение, за которым следует деление с остатком), приводит только к 27 умножениям и делениям целых чисел, которые все могут быть сохранены. в одном машинном слове. Как правило, любой из этих подходов требует менее $2log 2 (722340) \leq 40$ модульных умножений.

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

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

,

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

.

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

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

Перекодирование знаковых цифр [ править ]

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

Ссылки [ править ]

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

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

[frey-1] Перейти обратно: ^а ^б Коэн, Х.; Фрей, Г., ред. (2006). Справочник по криптографии эллиптических и гиперэллиптических кривых . Дискретная математика и ее приложения. Чепмен и Холл/CRC. ISBN 9781584885184 .

[ladder-3] Монтгомери, Питер Л. (1987). «Ускорение методов факторизации Полларда и эллиптических кривых» (PDF) . Математика. Вычислить . 48 (177): 243–264. doi : 10.1090/S0025-5718-1987-0866113-7 .

[4] Герон, Шей (5 апреля 2012 г.). «Эффективная программная реализация модульного возведения в степень» (PDF) . Журнал криптографической инженерии . 2 (1): 31–43. дои : 10.1007/s13389-012-0031-5 . S2CID 7629541 .

[1]

[примечания 1]

[2]

[3]

Основной метод [ править ]

Рекурсивная версия [ править ]

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

Вычислительная сложность [ править ]

2 к -арный метод [ править ]

Метод скользящего окна [ править ]

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

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

Метод Яо [ править ]

Евклидов метод [ править ]

Дальнейшие применения [ править ]

Перекодирование знаковых цифр [ править ]

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

См. также [ править ]

Примечания [ править ]

Ссылки [ править ]

2 ^к-арный метод [ править ]

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