Приветствую Вас, уважаемые Читатели! Вопрос, который я хочу сегодня рассмотреть на первый взгляд не имеет смысла: любая современная электронная вычислительная машина с легкостью справится с вычислением просто громадных степеней:
Однако, так было не всегда, и со временем перед математиками всё чаще вставал вопрос увеличения скорости вычислений, пусть даже проводимых вручную.
Например, в 15 веке персидский математик Гияс-ад-дин Джамшид ибн Масуд аль-Каши занимался излюбленной задачей математиков древности - вычислением числа π.
В «Трактате об окружности» аль-Каши вычисляет длину окружности по рецепту Архимеда - как среднее арифметическое между периметрами вписанного и описанного правильных многоугольников с количеством сторон 3 · 2^28, что дало ему для 2π приближение 6,2831853071795865.
Этим он поставил рекорд, продержавшийся до 1596 г., когда Людольф ван Цейлен вычислил число π с 35 десятичными знаками. Кроме того, наверняка можно сказать, что эта работа ал-Каши была первым исторически зафиксированным примером переведения дроби из одной системы счисления в другую.
Как он это сделал? С большой долей вероятности можно сказать, что этому поспособствовал придуманный им способ быстрого умножения в степень, который позже назовут дихотомическим или бинарным методом.
Сущность проблемы
Пусть в наличии два чиcла x и y, и требуется возвести одно в степень другого. Задача решается, как говорится, в лоб путем последовательного перемножения:
Все алгоритмы ускорения операции возведения в степень предполагают уменьшение количества умножений. Для данного случая мы могли бы воспользоваться свойствами степеней:
Мы получили некоторый выигрыш, но зачем он нужен, до сих пор не ясно. Всё станет предельно понятно, если мы обратимся к самому известному криптографическому алгоритму RSA, на основании которого сейчас, например, строится система цифровой подписи.
В этом алгоритме может потребоваться возводить числа в чудовищные степени.
Конечно, вычисления идут в кольце вычетов по модулю, однако решение таких задач в лоб либо приводит к числам, которые потребуют для хранения винчестер с количеством гигабайт, большим, чем число атомов во Вселенной, либо будут на настолько долго считаться, что к тому времени Вселенная "схлопнется".
Именно здесь и нашел применение (хотя уже со всевозможными модернизациями) алгоритм аль-Каши.
Бинарный алгоритм
Аль-Каши любил работать в разных системах счисления. Например, вычисления числа π он проводил в шестидесятеричной системе. Наш алгоритм, как можно догадаться, предусматривает представление степени числа в виде последовательностей 0 и 1.
Метод основан на достаточно простом наблюдении:
Эти вычисления повторяются рекурсивно до достижения результата:
Выигрыш очевиден: вместо шестнадцати умножений мы получили всего лишь 5! Если формально говорить о выигрыше, то алгоритмическая сложность стандартного и бинарного алгоритма возведения в степень выглядит так:
Для приведенного выше примера:
Именно столько потребовалось умножений для вычисления этой большого по рукописным и ничтожного по криптографическим меркам выражения. Так мы имеем исключительно возведение в квадрат и стандартные умножения, этот алгоритм легко переносится в двоичную систему счисления.
Модернизаций бинарного алгоритма огромное количество: где-то используется свойство повторяемости знаков при возведении в квадраты, метод скользящего окна, позволяющий разбить двоичную запись на удобные для вычисления блоки, метод Монтгомери, который защищает алгоритм от "атаки по времени".
Его суть заключается в том, что злоумышленник, наблюдающий за последовательностью возведения в квадрат и умножения, может (частично) восстановить показатель, участвующий в вычислении. Это большая проблема, если показатель степени должен оставаться секретным, как во многих криптосистемах с открытым ключом, например в RSA. Этот алгоритм более медленный, но маскирует показатель степени за счет некоторого количества "ложных" вычислений.
В реальной криптографии бинарный алгоритм используется уже в аспекте возведения в степень по модулю, т.к. прямое вычисление чисел уже слишком ресурсозатратно. Впрочем, это уже совсем другая история.
- Спасибо за внимание!