Алгоритмы быстрого возведения в степень
Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа в натуральную степень за меньшее число умножений, чем это требуется в определении степени[1]. Многие из этих алгоритмов основаны на том, что для возведения числа в степень не обязательно перемножать число на само себя раз, а можно перемножать уже вычисленные степени. В частности, если степень двойки, то для возведения в степень достаточно число возвести в квадрат раз, затратив при этом умножений вместо . Например, чтобы возвести число в восьмую степень, вместо выполнения семи умножений можно возвести число в квадрат (), потом результат возвести ещё раз в квадрат и получить четвёртую степень (), и наконец результат ещё раз возвести в квадрат и получить ответ ().
Кроме того, некоторые алгоритмы для дальнейшей оптимизации используют тот факт, что операция возведения в квадрат быстрее операции умножения за счёт того, что при возведении в квадрат цифры в сомножителе повторяются[2].
Бинарный алгоритм возведения в степень был впервые предложен в XV веке персидским математиком Аль-Каши[3].
Данные алгоритмы не всегда оптимальны. Например, при использовании схемы «слева направо» быстрое возведение в степень n = 15 потребует выполнения трёх операций умножения и трёх операций возведения в квадрат, хотя возведение в 15-ю степень можно выполнить и за 3 умножения и 2 возведения в квадрат[4]. Оптимальное возведение в степень соответствует построению кратчайшей аддитивной цепочки.
Описание
Основным алгоритмом быстрого возведения в степень является схема «слева направо». Она получила своё название вследствие того, что биты показателя степени просматриваются слева направо, то есть от старшего к младшему[5].
Пусть
- — двоичное представление степени n, то есть,
где . Тогда
- [5].
Последовательность действий при использовании данной схемы можно описать так:
- Представить показатель степени n в двоичном виде
- Если = 1, то текущий результат возводится в квадрат и затем умножается на x. Если = 0, то текущий результат просто возводится в квадрат[6]. Индекс i изменяется от k-1 до 0[7].
Таким образом, алгоритм быстрого возведения в степень сводится к мультипликативному аналогу схемы Горнера[6]:
Обобщения
Пусть пара (S, *) — полугруппа, тогда мы можем назвать операцию * умножением и определить операцию возведения в натуральную степень:
Тогда для вычисления значений an в любой полугруппе (в абелевой группе в частности) можно использовать алгоритмы быстрого возведения в степень[8].
Примеры решения задач
Применяя алгоритм, вычислим 2113:
Схема «справа налево»
В данной схеме, в отличие от схемы «слева направо», биты показателя степени просматриваются от младшего к старшему[5].
Последовательность действий при реализации данного алгоритма.
- Представить показатель степени n в двоичном виде.
- Положить вспомогательную переменную z равной числу x.
Данная схема содержит столько же умножений и возведений в квадрат, сколько и схема «слева направо». Однако несмотря на это, схема «слева направо» выгоднее схемы «справа налево», особенно в случае, если показатель степени содержит много единиц. Дело в том, что в схеме слева направо в операции result = result · x содержится постоянный множитель x. А для небольших x (что нередко бывает в тестах простоты) умножение будет быстрым. К примеру, для x = 2 мы можем операцию умножения заменить операцией сложения[7].
Математическое обоснование работы данного алгоритма можно представить следующей формулой:
- [9].
Пример. Посчитаем с помощью схемы возведения в степень «справа налево» значение 2113.
i | 0 | 1 | 2 | 3 |
---|---|---|---|---|
21 | 441 | 194 481 | 37 822 859 361 | |
1 | 0 | 1 | 1 |
- 21 · 194 481 = 4084 101
- 4084 101 · 37 822 859 361 = 154 472 377 739 119 461
Вычислительная сложность
И для схемы «слева направо», и для схемы «справа налево» количество операций возведения в квадрат одинаково и равно k, где k — длина показателя степени n в битах, . Количество же требуемых операций умножения равно весу Хэмминга, то есть количеству ненулевых элементов в двоичной записи числа n. В среднем требуется операций умножения[6].
Например, для возведения числа в сотую степень этим алгоритмом потребуется всего лишь 8 операций умножения и возведения в квадрат[5].
Для сравнения, при стандартном способе возведения в степень требуется операция умножения, то есть количество операций может быть оценено как [10].
Оптимизация алгоритма
Как правило, операция возведения в квадрат выполняется быстрее операции умножения. Метод окон позволяет сократить количество операций умножения и, следовательно, сделать алгоритм возведения в степень более оптимальным[8].
Окно фактически представляет собой основание системы счисления[7]. Пусть w — ширина окна, то есть за один раз учитывается w знаков показателя.
Рассмотрим метод окна.
- Для заранее вычисляется xi
- Показатель степени представляется в следующем виде: , где
- Пусть y — переменная, в которой будет вычислен конечный результат. Положим .
- Для всех i = k/w — 1, k/w — 2, …, 0 выполнить следующие действия:
- [8].
В данном алгоритме требуется k возведений в квадрат, но число умножений в среднем сокращается до k/w[8].
Ещё более эффективным является метод скользящего окна. Он заключается в том, что ширина окна во время выполнения процесса может изменяться:
- Показатель степени представляется в виде , где , а ei+1 — ei ≥ w.
- Для вычисляется xi. Далее будем обозначать xi как xi.
- Пусть y — переменная, в которой будет вычислен конечный результат. Положим .
- Для всех i = l — 1, l — 2, …, 0 выполнить следующие действия:
- Для всех j от 0 до ei+1 — ei — 1 y возвести в квадрат
- Для всех j от 0 до e0 — 1 y возвести в квадрат[8].
Количество операций возведения в степень в данном алгоритме такое же, как и в методе окна, а вот количество операций умножений сократилось до l, то есть до в среднем[8].
Для примера возведём методом скользящего окна число x в степень 215. Ширина окна w = 3.
- 215 = 27 + 5 · 24 + 7
- y = 1
- y = y · x = x
- y 3 раза возводится в квадрат, так как на данном шаге e2 — e1 −1 = 7 — 4 — 1 = 2, а отсчёт ведётся с нуля, то есть y = y8 = x8
- y = y · x5 = x13
- y 4 раза возводится в квадрат, так как на данном шаге e1 — e0 −1 = 4 — 0 — 1 = 3, то есть y = y16= x208
- y = y · x7 = x215
Применение
Алгоритм быстрого возведения в степень получил широкое распространение в криптосистемах с открытым ключом. В частности, алгоритм применяется в протоколе RSA, схеме Эль-Гамаля и других криптографических алгоритмах[11].
См. также
Примечания
- ↑ Швец А. Н. Быстрое возведение в степень . Дата обращения: 13 ноября 2015. Архивировано 17 ноября 2015 года.
- ↑ Панкратова, 2009, с. 7.
- ↑ Панкратова, 2009, с. 11.
- ↑ Панкратова, 2009, с. 10.
- ↑ 1 2 3 4 Рябко, Фионов, 2004.
- ↑ 1 2 3 4 Handbook, 2006.
- ↑ 1 2 3 4 Крэндалл, Померанс, 2011.
- ↑ 1 2 3 4 5 6 Криптография, 2005.
- ↑ Габидулин, Кшевецкий, Колыбельников, 2011.
- ↑ Маховенко, 2006.
- ↑ Прикладная криптография, 2002.
Литература
- Шнайер Б. Алгоритмы с открытыми ключами // Прикладная криптография. — Триумф, 2002. — ISBN 5-89392-055-4.
- Рябко Б. Я., Фионов А. Н. Основы современной криптографии для специалистов в информационных технологиях — Научный мир, 2004. — С. 15. — 173 с. — ISBN 978-5-89176-233-6
- Смарт Н. Алгоритмы возведения в степень // Криптография. — Москва: Техносфера, 2005. — С. 287—292. — 528 с. — ISBN 5-94836-043-1.
- Маховенко Е. Б. Теоретико-числовые методы в криптографии — М.: Гелиос АРВ, 2006. — С. 154—155. — ISBN 978-5-85438-143-7
- Cohen H., Frey G. Handbook of Elliptic and Hyperelliptic Curve Cryptography. — Chapman & Hall/CRC, 2006. — С. 145—150. — 808 с. — ISBN 1-58488-518-1.
- Панкратова И. А. Теоретико-числовые методы криптографии — Томск: ТГУ, 2009. — 120 с.
- Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — С. 230—231. — 225 с. — ISBN 978-5-7417-0377-9
- Крэндалл Р., Померанс К. Алгоритмы с открытыми ключами // Простые числа: Криптографические и вычислительные аспекты — М.: URSS, 2011. — С. 514—520. — 663 с. — ISBN 978-5-453-00016-6, 978-5-397-02060-2