Эта статья входит в число добротных статей

Алгоритмы быстрого возведения в степень

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритмы быстрого возведения в степень (Дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа x в натуральную степень n за меньшее число умножений, чем это требуется в определении степени[1]. Алгоритмы основаны на том, что для возведения числа x в степень n не обязательно перемножать число x на само себя n раз, а можно перемножать уже вычисленные степени. Так, например, если n=2^k степень двойки, то для возведения в степень n достаточно число возвести в квадрат k раз, затратив при этом k умножений вместо 2^k. Кроме того, некоторые алгоритмы для дальнейшей оптимизации используют тот факт, что операция возведения в квадрат быстрее операции умножения за счёт того, что при возведении в квадрат цифры в сомножителе повторяются[2].

Бинарный алгоритм возведения в степень был впервые предложен в XV веке персидским математиком Аль-Каши[3].

Данные алгоритмы не всегда оптимальны. Например, при использовании схемы «слева-направо» быстрое возведение в степень n = 15 потребует выполнения трёх операций умножения и трёх операций возведения в квадрат, хотя возведение в 15-ю степень можно выполнить и за 3 умножения и 2 возведения в квадрат[4].

Описание[править | править вики-текст]

Основным алгоритмом быстрого возведения в степень является схема «слева направо». Она получила своё название вследствие того, что биты показателя степени просматриваются слева направо, то есть от старшего к младшему[5].

Пусть

n=(\overline {m_{k}m_{k-1}...m_{1}m_{0}})_2 — двоичное представление степени n, то есть,
n=m_{k} \cdot 2^{k}+m_{k-1} \cdot 2^{k-1}+\dots+m_{1} \cdot 2+m_{0},

где m_{k}=1, m_{i} \in \{ 0,1 \}. Тогда

x^{n}=x^{((\dots((m_{k} \cdot 2+m_{k-1}) \cdot 2+m_{k-2}) \cdot 2+\dots) \cdot 2+m_{1}) \cdot 2 + m_{0}}=((\dots(((x^{m_{k}})^{2} \cdot x^{m_{k-1}})^{2}\dots)^{2} \cdot x^{m_{1}})^2 \cdot x^{m_{0}}[5].

Последовательность действий при использовании данной схемы можно описать так:

  1. Представить показатель степени n в двоичном виде
  2. Если m_i = 1 то текущий результат умножается на x и затем возводится в квадрат. Если m_i = 0, то текущий результат просто возводится в квадрат[6]. Индекс i изменяется от k-1 до 0[7].

Таким образом, алгоритм быстрого возведения в степень сводится к мультипликативному аналогу схемы Горнера[6]:

\begin{Bmatrix} s_1=x \\ s_{i+1}=s_i^2 \cdot x^{m_{k-i}} \\ i=1,2,\dots,k \end{Bmatrix}.

Обобщения[править | править вики-текст]

Пусть пара (S, *) — полугруппа, тогда мы можем назвать операцию * умножением и определить операцию возведения в натуральную степень:

a^n=\left\{ \begin{array}{ll} a & n = 1 \\ a * \left(a^{n-1}\right) & n > 1 \end{array} \right.

Тогда для вычисления значений an в любой полугруппе (в абелевой группе в частности) можно использовать алгоритмы быстрого возведения в степень[8].

Примеры решения задач[править | править вики-текст]

Применяя алгоритм, вычислим 2113:

13_{10} = 1101_2


\begin{align} 21^{13} & = (((21^2)\cdot21)^2)^2\cdot21 \\ & = ((441\cdot21)^2)^2\cdot21 \\ & = 85766121^2\cdot21 \\ & = 154472377739119461 \end{align}

Схема «справа налево»[править | править вики-текст]

В данной схеме, в отличие от схемы «слева направо», биты показателя степени просматриваются от младшего к старшему[5].

Последовательность действий при реализации данного алгоритма.

  1. Представить показатель степени n в двоичном виде.
  2. Положить вспомогательную переменную z равной числу x.
    1. Если m_i, = 1 то текущий результат умножается на z, а само число z возводится в квадрат. Если m_i = 0, то требуется только возвести z в квадрат[6]. При этом индекс i, в отличие от схемы слева направо, изменяется от 0 до k-1 включительно[7].

Данная схема содержит столько же умножений и возведений в квадрат, сколько и схема «слева направо». Однако несмотря на это, схема «слева направо» выгоднее схемы «справа налево», особенно в случае, если показатель степени содержит много единиц. Дело в том, что в схеме слева направо в операции result = result · x содержится постоянный множитель x. А для небольших x (что нередко бывает в тестах простоты) умножение будет быстрым. К примеру, для x = 2 мы можем операцию умножения заменить операцией сложения[7].

Схема с предварительным вычислением[править | править вики-текст]

Другим вариантом является схема, в которой предварительно вычисляются числа вида a^{2^{i}}. Её можно представить следующей формулой:

d = a^n =
= a^{\sum_{i=0}^k m_i\cdot 2^i} =
= a^{m_0}\cdot a^{2m_1}\cdot a^{2^2*m_2}\cdot ... \cdot a^{2^k*m_k}=
= a^{m_0}\cdot (a^2)^{m_1}\cdot (a^{2^2})^{m_2}\cdot ... \cdot (a^{2^k})^{m_k}=
 = \prod_{i=0}^k {(a^{2^{i}})^{m_i}}[9].

Таким образом, последовательность действий в данной схеме следующая:

  1. Вычислить все числа вида a^{2^{i}}, где i=\overline {0, k} и сохранить их в памяти;
  2. Представить показатель степени в двоичном виде;
  3. Если i-й бит показателя степени равен 1, то умножаем текущий результат на a^{2^{i}}[5].

Недостатком данной схемы служит необходимость хранения в памяти результатов предварительных вычислений[5].

Пример. Посчитаем с помощью схемы возведения в степень «справа налево» значение 2113.

i 0 1 2 3
a^{2^{i}} 21 441 194 481 37 822 859 361
m_1 1 0 1 1
  1. 21 · 194 481 = 4084 101
  2. 4084 101 · 37 822 859 361 = 154 472 377 739 119 461

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

И для схемы «слева направо», и для схемы «справа налево» количество операций возведения в квадрат одинаково и равно k, где k — длина показателя степени n в битах, k \sim \ln{n}. Количество же требуемых операций умножения равно весу Хэмминга, то есть количеству ненулевых элементов в двоичной записи числа n. В среднем требуется \frac{1}{2}\cdot\ln{n} операций умножения[6].

Например, для возведения числа в сотую степень этим алгоритмом потребуется всего лишь 8 операций умножения и возведения в квадрат[5].

Для сравнения, при стандартном способе возведения в степень требуется n-1 операция умножения, то есть количество операций может быть оценено как  O(n) [10].

Оптимизация алгоритма[править | править вики-текст]

Как правило операция возведения в квадрат выполняется быстрее операции умножения. Метод окон позволяет сократить количество операций умножения и, следовательно, сделать алгоритм возведения в степень более оптимальным[8].

Окно фактически представляет собой основание системы счисления[7]. Пусть w - ширина окна, т.е. за один раз учитывается w знаков показателя.

Рассмотрим метод окна.

  1. Для i = \overline {0, 2^w-1} заранее вычисляется xi
  2. Показатель степени представляется в следующем виде: n = \sum_{i=0}^{k/w}{n_i\cdot2^{i\cdot w}}, где n_i \in {(0, 1, ..., 2^w-1)}
  3. Пусть y — переменная, в которой будет вычислен конечный результат. Положим y=x^{n_{k/w}}.
  4. Для всех i = k/w - 1, k/w - 2, ..., 0 выполнить следующие действия:
    1. y = y^{2^w}
    2. y = y\cdot x^{n_i}[8].

В данном алгоритме требуется k возведений в квадрат, но число умножений в среднем сокращается до k/w[8].

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

  1. Показатель степени представляется в виде n = \sum_{i=0}^{l}{n_i\cdot2^{e_i}}, где n_i \in {(1, 3, 5, ..., 2^w-1)}, а ei+1 - eiw.
  2. Для i = (1, 3, 5, ..., 2^w-1) вычисляется xi. Далее будем обозначать xi как xi.
  3. Пусть y — переменная, в которой будет вычислен конечный результат. Положим y=x^{n_{l}}.
  4. Для всех i = l - 1, l - 2, ..., 0 выполнить следующие действия:
    1. Для всех j от 0 до ei+1 - ei - 1 y возвести в квадрат
    2. j = m_i
    3. y = y\cdot x_j
  5. Для всех j от 0 до e0 - 1 y возвести в квадрат[8].

Количество операций возведения в степень в данном алгоритме такое же, как и в методе окна, а вот количество операций умножений сократилось до l, то есть до \frac{k}{w+1} в среднем[8].

Для примера возведём методом скользящего окна число x в степень 215. Ширина окна w = 3.

  1. 215 = 27 + 5 · 24 + 7
  2. y = 1
  3. y = y · x = x
  4. y 3 раза возводится в квадрат, т.к. на данном шаге e2 - e1 -1 = 7 - 4 - 1 = 2, а отсчёт ведётся с нуля, т.е. y = y8 = x8
  5. y = y · x5 = x13
  6. y 4 раза возводится в квадрат, т.к. на данном шаге e1 - e0 -1 = 4 - 0 - 1 = 3, т.е. y = y16= x208
  7. y = y · x7 = x215

Применение[править | править вики-текст]

Алгоритм быстрого возведения в степень получил широкое распространение в криптосистемах с открытым ключом. В частности, алгоритм применяется в протоколе RSA, схеме Эль-Гамаля и других криптографических алгоритмах[11].

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

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

  • Панкратова И. А. Теоретико-числовые методы криптографии. — Томск: Томский государственный университет, 2009. — С. 8. — 120 с.
  • Рябко Б. Я., Фионов А. Н. Основы современной криптографии для специалистов в информационных технологиях. — Научный мир, 2004. — С. 15. — 173 с. — ISBN 5-89176-233-1.
  • Смарт Н. Алгоритмы возведения в степень // Криптография. — Москва: Техносфера, 2005. — С. 287-292. — 528 с. — ISBN 5-94836-043-1.
  • Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации. — Москва: МФТИ, 2011. — С. 230-231. — 262 с. — ISBN 978-5-7417-0377-9.
  • Маховенко Е. Б. Теоретико-числовые методы в криптографии. — Москва: Гелиос АРВ, 2006. — С. 154-155. — 320 с. — ISBN 5-85438-143-5.
  • Шнайер Б. Алгоритмы с открытыми ключами // Прикладная криптография. — Триумф, 2002. — ISBN 5-89392-055-4.
  • Крэндалл Р., Померанс К. Алгоритмы с открытыми ключами // Простые числа: криптографические и вычислительные аспекты. — Москва: URSS, 2011. — С. 514-520. — 664 с. — ISBN 978-5-453-00016-6.
  • Cohen H., Frei G. Handbook of Elliptic and Hyperelliptic Curve Cryptography. — Chapman & Hall/CRC, 2006. — С. 145-150. — 808 с. — ISBN 1-58488-518-1.