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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален.
Найти источники: «Возведение в степень возведением в квадрат» - новости · газеты · книги · ученый · JSTOR ( февраль 2018 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

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

Этот раздел может сбивать с толку или непонятно читателям . В частности, в примере описывается алгоритм, отличный от алгоритма оставшейся части раздела, поскольку биты показателя степени рассматриваются в противоположном порядке. Помогите, пожалуйста, прояснить раздел . На странице обсуждения может быть обсуждение этого вопроса . ( Апрель 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Метод основан на наблюдении, что для положительного целого 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 в двоичной системе равен 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})}

r\leftarrow r\cdot x\,(=x^{3})

Шаг 3) ; бит 3 = 0, поэтому мы закончили этот шаг (эквивалентно, это соответствует );

r\leftarrow r^{2}\,(=x^{6})

r\leftarrow r\cdot x^{0}\,(=x^{6})

Шаг 4) ; бит 4 = 1, поэтому вычислим .

r\leftarrow r^{2}\,(=x^{12})

r\leftarrow r\cdot x\,(=x^{13})

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

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

 Функция  exp_by_squaring ( х ,  п ) ,  если  п  <  0 ,  то  возвращают  exp_by_squaring ( 1  /  х ,  - п ) ;  остальное ,  если  п  =  0 ,  то  возвращает  1 ;  остальное ,  если  п  =  1 ,  то  возвращают  х  ;  иначе ,  если  п  будет  даже  тогда  вернуть  exp_by_squaring ( х  *  х , п  /  2 ) ;  остальное ,  если  п  является  нечетным ,  то  возвращают  х  *  exp_by_squaring ( х  *  х ,  ( п  -  1 )  /  2 ) ;

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

 Функция  exp_by_squaring ( х ,  п )  возвращение  exp_by_squaring2 ( 1 ,  х ,  п )  Функция  exp_by_squaring2 ( у ,  х ,  п ) ,  если  п  <  0 ,  то  возвращают  exp_by_squaring2 ( у ,  1  /  х ,  -  п ) ;  иначе ,  если  п  =  0 ,  то  возвращают  у ;  иначе  если n  =  1,  затем  вернуть  x  *  y ;  остальное ,  если  п  будет  даже  тогда  возвращать  exp_by_squaring2 ( у ,  х  *  х ,  п  /  2 ) ;  остальное ,  если  п  является  нечетным ,  то  возвращают  exp_by_squaring2 ( х  *  у ,  х  *  х ,  ( п  -  1 )  /  2 ) .

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

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 )  _ ехр  x  n  x  1

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

 Функция  exp_by_squaring_iterative ( x ,  n ),  если  n  <  0,  то  x  : =  1  /  x ;  n  : =  - n ;  если  п  =  0 ,  то  возвращают  1  у  : =  1 ; в  то время как  п  >  1  делать ,  если  п  является  даже  тогда  х  : =  х  *  х ;  n  : =  n  /  2 ; иначе  y  : =  x  *  y ;  х  : =  х  *  х ;  п  : =  ( п  -  1 )  /  2 ;  вернуть  x  *  y

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

Краткий анализ показывает, что такой алгоритм использует квадраты и не более чем умножения, где обозначает функцию пола . Точнее, количество умножений на единицу меньше количества единиц, присутствующих в двоичном разложении числа 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 с ты странный.

Алгоритм:

Вход: Элемент 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

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

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

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

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

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

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

Алгоритм:

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

Техника лестницы Монтгомери [ править ]

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

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

х ₁ = х; x ₂ = x ²для i = k - от 2 до 0 do  Если n _i = 0, то 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 = 2 k$ и $b i = h i$ , тогда значения $n i$ будут просто цифрами $n$ в базе $h$ . Метод Яо собирает в u сначала те $x i,$ которые появляются в высшей степени ; в следующем раунде те, у кого есть мощность , также собираются в $u$ и т. д. Переменная y умножается на начальное $u$ , умножается на следующие наибольшие степени и так далее. Алгоритм использует умножения и $h-1$ $h-2$ $h-1$ $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 по$ $модулю$ $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}}}$

Начать цикл  Find ,  $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 }$ . Тогда он поднимает $е М$ к источнику $д$ , умножает это значение с $й N$ , а затем присваивает $й г N$ результата этого вычисления и $п М$ значения $п М$ по модулю $п Н$ .

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

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

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

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

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

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

потребовалось бы очень много времени и много места для хранения, если бы использовался простой метод: вычислите 13789 ⁷²²³⁴¹ , затем возьмите остаток при делении на 2345. Даже использование более эффективного метода займет много времени: возведите 13789 в квадрат, возьмите остаток при делении на 2345, умножьте результат на 13789 и так далее. Это займет меньше, чем модульное умножение. $2\log _{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 в$ виде цифр со знаком как

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

Знаковое двоичное представление соответствует конкретному выбору $b = 2$ и . Обозначается он . Есть несколько методов вычисления этого представления. Представление не уникальное. Например, возьмем $n$ $= 478$ : два различных знаковых двоичных представления даны как и , где используется для обозначения $-1$ . Поскольку двоичный метод вычисляет умножение для каждой ненулевой записи в представлении $n$ по основанию 2 , мы заинтересованы в поиске двоичного представления со знаком с наименьшим числом ненулевых элементов, то есть с минимальным значением Хэмминга. масса $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}}$ . Один из способов сделать это - вычислить представление в несмежной форме , или сокращенно NAF, которая удовлетворяет и обозначается как . Например, представление NAF для 478 - это . Это представление всегда имеет минимальный вес Хэмминга. Простой алгоритм для вычисления представления NAF данного целого числа с состоит в следующем: $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$ для  $я = 0$  до  $л - 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, заканчивающуюся ненулевым значением. Не все нечетные степенидвойки, которые необходимо вычислить, необходимо учитывать только те, которые конкретно участвуют в вычислении. $x^{2^{k}-1}$

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

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

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

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

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

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

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

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

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

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

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

Техника лестницы Монтгомери [ править ]

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

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

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

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

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

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

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

Заметки [ править ]

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

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