stringtranslate.com

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

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

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

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

Метод основан на наблюдении, что для любого целого числа имеем:

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

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

В: целое число 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 . Это логарифмическое число операций следует сравнить с тривиальным алгоритмом, который требует n1 умножений.

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

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

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

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

Если применить эту формулу рекурсивно, начиная с 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                                                           

Корректность алгоритма обусловлена ​​тем, что является инвариантным в ходе вычислений: он находится в начале и он находится в конце.

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

Сложность вычислений

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

Каждое возведение в квадрат дает примерно удвоенное количество цифр по сравнению с предыдущим, и поэтому, если умножение двух d -значных чисел реализуется за O( d k ) операций для некоторого фиксированного k , то сложность вычисления x n определяется выражением

2к-арный метод

Этот алгоритм вычисляет значение x n после разложения показателя степени по основанию 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 0 ) 2 k и предварительно вычисленные значения .
Выход
Элемент x n в 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]

Метод раздвижного окна

Этот метод является эффективным вариантом 2 k -арного метода. Например, чтобы вычислить показатель степени 398, который имеет двоичное расширение (110 001 110) 2 , мы берем окно длиной 3, используя алгоритм 2 k -арного метода, и вычисляем 1, x 3 , x 6 , x 12 , x 24 , x 48 , x 49 , x 98 , x 99 , x 198 , x 199 , x 398 . Но мы также можем вычислить 1, x 3 , x 6 , x 12 , x 24 , x 48 , x 96 , x 192 , x 199 , x 398 , что экономит одно умножение и равносильно оценке (110 001 110) 2

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

Алгоритм:

Вход
Элемент x из G , неотрицательное целое число n =( n l −1 , n l −2 , ..., n 0 ) 2 , параметр k > 0 и предварительно вычисленные значения .
Выход
Элемент x nG .

Алгоритм:

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 0 ) 2 с n k−1 = 1, мы можем вычислить x n следующим образом:

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 запишется как

где для всех .

Пусть x i = x b i .

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

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

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

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

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

где . Другими словами, евклидово деление показателя степени n 1 на n 0 используется для возврата частного q и остатка n 1 mod n 0 .

Учитывая базовый элемент x в группе G и показатель степени, записанный так, как в методе Яо, элемент вычисляется с использованием предварительно вычисленных значений , а затем алгоритма, приведенного ниже.

Начать цикл  Найти ,  такой что .  Найти ,  такой что .  Прервать цикл,  если .  Пусть ,  а затем пусть .  Вычислить рекурсивно ,  а затем пусть . Конец цикла ; Возврат .

Алгоритм сначала находит наибольшее значение среди n i , а затем супремум в пределах множества { n i \ iM } . Затем он возводит x M в степень q , умножает это значение на x N , а затем присваивает x N результат этого вычисления и n M значение n M по модулю n N .

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

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

13789 722341 (мод. 2345) = 2029

потребовало бы очень много времени и места для хранения, если бы использовался наивный метод вычисления 13789 722341 и последующего взятия остатка от деления на 2345. Даже использование более эффективного метода заняло бы много времени: возвести 13789 в квадрат, взять остаток от деления на 2345, умножить результат на 13789 и т. д.

Применение вышеприведенного алгоритма exp-by-squared , где "*" интерпретируется как x * y = xy mod 2345 (то есть умножение, за которым следует деление с остатком), приводит всего к 27 умножениям и делениям целых чисел, которые все могут быть сохранены в одном машинном слове. Как правило, любой из этих подходов потребует менее 2log 2 (722340) ≤ 40 модульных умножений.

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

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

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

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

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

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

Для этого мы определяем знаковое цифровое представление целого числа n в системе счисления с основанием b как

Знаковое двоичное представление соответствует частному выбору b = 2 и . Оно обозначается как . Существует несколько методов вычисления этого представления. Представление не является уникальным. Например, возьмем n = 478 : два различных знаковых двоичных представления задаются как и , где используется для обозначения −1 . Поскольку двоичный метод вычисляет умножение для каждого ненулевого элемента в представлении n с основанием 2 , мы заинтересованы в нахождении знакового двоичного представления с наименьшим количеством ненулевых элементов, то есть с минимальным весом Хэмминга . Один из методов сделать это состоит в вычислении представления в несмежной форме , или сокращенно NAF, которая удовлетворяет и обозначается как . Например, представление NAF числа 478 равно . Это представление всегда имеет минимальный вес Хэмминга. Простой алгоритм вычисления представления NAF заданного целого числа с помощью следующий:

для i = 0 до l − 1 сделать возврат 

Другой алгоритм Коямы и Цуруоки не требует выполнения условия ; он по-прежнему минимизирует вес Хэмминга.

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

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

 (возведение в квадрат, умножение на 6),
 (оптимальная цепочка сложения, 5 умножается, если x 3 используется повторно).

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

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

Примечания

  1. ^ В этой строке цикл находит самую длинную строку длины, меньшей или равной k , заканчивающуюся ненулевым значением. Не все нечетные степени 2 до нужно вычислять, а только те, которые конкретно участвуют в вычислении, нужно учитывать.

Ссылки

  1. ^ ab Cohen, H.; Frey, G., ред. (2006). Справочник по эллиптической и гиперэллиптической криптографии . Дискретная математика и ее приложения. Chapman & Hall/CRC. ISBN 9781584885184.
  2. ^ Монтгомери, Питер Л. (1987). «Ускорение методов Полларда и эллиптической кривой факторизации» (PDF) . Math. Comput . 48 (177): 243–264. doi : 10.1090/S0025-5718-1987-0866113-7 .
  3. ^ Gueron, Shay (5 апреля 2012 г.). "Эффективные программные реализации модульного возведения в степень" (PDF) . Journal of Cryptographic Engineering . 2 (1): 31–43. doi :10.1007/s13389-012-0031-5. S2CID  7629541.