Этот алгоритм придумали в XV веке, но раскрыли истинный потенциал лишь недавно. Бинарное возведение в степень

На это вычисление понадобился всего лишь «миг»

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

Например, в 15 веке персидский математик Гияс-ад-дин Джамшид ибн Масуд аль-Каши занимался излюбленной задачей математиков древности — вычислением числа π.

Именно этому человеку мы обязаны появлением такого понятия, как «десятичная дробь», а еще он составил огромное количество тригонометрических таблиц с точностью до 8 знаков и на 100 лет опередил «прогрессивную» Европу в деле приближенного решения кубических уравнений.

В «Трактате об окружности» аль-Каши вычисляет длину окружности по рецепту Архимеда — как среднее арифметическое между периметрами вписанного и описанного правильных многоугольников с количеством сторон 3 · 2^28, что дало ему для 2π приближение 6,2831853071795865.

Этим он поставил рекорд, продержавшийся до 1596 г., когда Людольф ван Цейлен вычислил число π с 35 десятичными знаками. Кроме того, наверняка можно сказать, что эта работа ал-Каши была первым исторически зафиксированным примером переведения дроби из одной системы счисления в другую.

Как он это сделал? С большой долей вероятности можно сказать, что этому поспособствовал придуманный им способ быстрого умножения в степень, который позже назовут дихотомическим или бинарным методом.

Сущность проблемы

Пусть в наличии два чиcла x и y, и требуется возвести одно в степень другого. Задача решается, как говорится, в лоб путем последовательного перемножения:

Все алгоритмы ускорения операции возведения в степень предполагают уменьшение количества умножений. Для данного случая мы могли бы воспользоваться свойствами степеней:

Мы получили некоторый выигрыш, но зачем он нужен, до сих пор не ясно. Всё станет предельно понятно, если мы обратимся к самому известному криптографическому алгоритму RSA, на основании которого сейчас, например, строится система цифровой подписи.

В этом алгоритме может потребоваться возводить числа в чудовищные степени.

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

Для примера, какие степени могут реально вычисляться. А ведь это нужно делать максимально быстро!

Именно здесь и нашел применение (хотя уже со всевозможными модернизациями) алгоритм аль-Каши.

Бинарный алгоритм

Аль-Каши любил работать в разных системах счисления. Например, вычисления числа π он проводил в шестидесятеричной системе. Наш алгоритм, как можно догадаться, предусматривает представление степени числа в виде последовательностей 0 и 1.

Метод основан на достаточно простом наблюдении:

Эти вычисления повторяются рекурсивно до достижения результата:

Если разбирать по-другому, то: количество умножений равно весу Хэмминга показателя степени в двоичном виде (17 = 10001, вес = кол-во единиц = 2) минус 1. Т.е. требуется только одно умножение (на рисунке под пятым номером). Кроме того требуется |_log₂n_| возведений в квадрат — 4

Выигрыш очевиден: вместо шестнадцати умножений мы получили всего лишь 5! Если формально говорить о выигрыше, то алгоритмическая сложность стандартного и бинарного алгоритма возведения в степень выглядит так:

n-1 операций умножения потребуется в стандартном способе, в О-нотации говорят, что сложность пропорциональна n и единицу не учитывают. А вот степени и логарифмы уже серьезно влияют на сложность. В принципе и функцию потолка можно опустить в этой записи

Для приведенного выше примера:

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

Модернизаций бинарного алгоритма огромное количество: где-то используется свойство повторяемости знаков при возведении в квадраты, метод скользящего окна, позволяющий разбить двоичную запись на удобные для вычисления блоки, метод Монтгомери, который защищает алгоритм от «атаки по времени».

Его суть заключается в том, что злоумышленник, наблюдающий за последовательностью возведения в квадрат и умножения, может (частично) восстановить показатель, участвующий в вычислении. Это большая проблема, если показатель степени должен оставаться секретным, как во многих криптосистемах с открытым ключом, например в RSA. Этот алгоритм более медленный, но маскирует показатель степени за счет некоторого количества «ложных» вычислений.

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

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