Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

Алгоритмы быстрого возведения в степень (дихотомическийалгоритм возведения в степень, бинарный алгоритм возведения в степень)— алгоритмы, предназначенные для возведения числа x внатуральную степень n за меньшее число умножений, чем этотребуется в определении степени. Алгоритмы основаны на том, что длявозведения числа x в степень n не обязательно перемножатьчисло x на само себя n раз, а можно перемножать ужевычисленные степени. Так, например, если n=2k степень двойки, то длявозведения в степень n достаточно число возвести в квадрат kраз, затратив при этом k умножений вместо 2k. Кроме того,некоторые алгоритмы для дальнейшей оптимизации используют тот факт, чтооперация возведения в квадрат быстрее операции умножения за счёт того,что при возведении в квадрат цифры в сомножителе повторяются.
 Бинарный алгоритм возведения в степень был впервые предложен в XV векеперсидским математиком Аль-Каши.
 Данные алгоритмы не всегда оптимальны. Например, при использовании схемы«слева-направо» быстрое возведение в степень n = 15 потребуетвыполнения трёх операций умножения и трёх операций возведения в квадрат,хотя возведение в 15-ю степень можно выполнить и за 3 умножения и 2возведения в квадрат.

Описание


 Основным алгоритмом быстрого возведения в степень является схема «слеванаправо». Она получила своё название вследствие того, что битыпоказателя степени просматриваются слева направо, то есть от старшего кмладшему.
 Пусть
n=(¯mkmk1...m1m0)2 — двоичноепредставление степени n, то есть,

n=mk2k+mk12k1++m12+m0,
 где mk=1,mi{0,1}. Тогда

xn=x((((mk2+mk1)2+mk2)2+)2+m1)2+m0=(((((xmk)2xmk1)2)2xm1)2xm0.
 Последовательность действий при использовании данной схемы можно описатьтак:

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

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

{s1=xsi+1=s2ixmkii=1,2,,k}.

Обобщения


 Пусть пара (S, *) — полугруппа, тогда мы можем назватьоперацию * умножением и определить операцию возведения в натуральнуюстепень:
an={an=1a(an1)n>1
 Тогда для вычисления значений an влюбой полугруппе (в абелевой группе в частности) можно использоватьалгоритмы быстрого возведения в степень.

Примеры решениязадач


 Применяя алгоритм, вычислим 2113:
1310=11012
2113=(((212)21)2)221=((44121)2)221=85766121221=154472377739119461

Схема «справаналево»


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

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

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

Схема с предварительнымвычислением


 Другим вариантом является схема, в которой предварительно вычисляютсячисла вида a2i. Её можно представить следующей формулой:
d=an=
=aki=0mi2i=
=am0a2m1a22m2...a2kmk=
=am0(a2)m1(a22)m2...(a2k)mk=
=ki=0(a2i)mi.
 Таким образом, последовательность действий в данной схеме следующая:

  1. Вычислить все числа вида a2i, где i=¯0,k и сохранить их в памяти;
  2. Представить показатель степени в двоичном виде;
  3. Если i-й бит показателя степени равен 1, то умножаем текущий результат на a2i.

 Недостатком данной схемы служит необходимость хранения в памятирезультатов предварительных вычислений.
Пример. Посчитаем с помощью схемы возведения в степень «справаналево» значение 2113.
i0123
a2i21441194 48137 822 859 361
m11011


  1. 21 · 194 481 = 4084 101
  2. 4084 101 · 37 822 859 361 = 154 472 377 739 119 461

Вычислительнаясложность


 И для схемы «слева направо», и для схемы «справа налево» количествоопераций возведения в квадрат одинаково и равно k, где k— длина показателя степени n в битах, klnn.Количество же требуемых операций умножения равно весу Хэмминга, то естьколичеству ненулевых элементов в двоичной записи числа n. Всреднем требуется 12lnn операций умножения.
 Например, для возведения числа в сотую степень этим алгоритмомпотребуется всего лишь 8 операций умножения и возведения в квадрат.
 Для сравнения, при стандартном способе возведения в степень требуетсяn1 операция умножения, то есть количество операций может быть оцененокак O(n).

Оптимизацияалгоритма


 Как правило операция возведения в квадрат выполняется быстрее операцииумножения. Метод окон позволяет сократить количество операций умноженияи, следовательно, сделать алгоритм возведения в степень болееоптимальным.
 Окно фактически представляет собой основание системы счисления. Пустьw - ширина окна, т.е. за один раз учитывается w знаковпоказателя.
 Рассмотрим метод окна.

  1. Для i=¯0,2w1 заранее вычисляется xi
  2. Показатель степени представляется в следующем виде: n=k/wi=0ni2iw, где ni(0,1,...,2w1)
  3. Пусть y — переменная, в которой будет вычислен конечный результат. Положим y=xnk/w.
  4. Для всех i = k/w - 1, k/w - 2, ..., 0 выполнить следующие действия:
    1. y=y2w
    2. y=yxni.

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

  1. Показатель степени представляется в виде n=li=0ni2ei, где ni(1,3,5,...,2w1), а ei+1 - eiw.
  2. Для i=(1,3,5,...,2w1) вычисляется xi. Далее будем обозначать xi как xi.
  3. Пусть y — переменная, в которой будет вычислен конечный результат. Положим y=xnl.
  4. Для всех i = l - 1, l - 2, ..., 0 выполнить следующие действия:
    1. Для всех j от 0 до ei+1 - ei - 1 y возвести в квадрат
    2. j=mi
    3. y=yxj

  5. Для всех j от 0 до e0 - 1 y возвести в квадрат.

 Количество операций возведения в степень в данном алгоритме такое же,как и в методе окна, а вот количество операций умножений сократилось доl, то есть до kw+1 в среднем.
 Для примера возведём методом скользящего окна число 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, схеме Эль-Гамаля и других криптографических алгоритмах.