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

Должен сразу признаться, что статья не будет посвящена тому, как русским крестьянам удавалось обмениваться информацией втайне от своих помещиков.

Умножение методом русских крестьян

Если вы не знали о нём раньше, то это довольно любопытный подход к умножению, который не требует запоминания таблиц умножения — для него достаточно способности удваивать и делить пополам целые числа. Не очень понятно, как он относится к русским крестьянам: похоже, так же, как «датская сдоба» к Дании. Этот метод был известен ещё древним египтянам, которые явно жили намного раньше русских крестьян.

Общее описание метода просто, но не слишком информативно. Тем не менее, давайте начнём с него.

Если нам нужно перемножить два целых числа $$ и $$, то мы начертим две колонки, в заголовке одной напишем $$, а в другой — $$. Затем начнём постоянно добавлять новые ряды, получаемые делением пополам $$ (остаток отбрасывается) и удвоением $$, и остановимся, когда в колонке $$ останется $$. Наконец, сложим все элементы колонки $$, где значение $$ нечётно.

Гораздо понятнее всё станет, если привести пример. Так что давайте выполним умножение $$. Это даёт нам таблицу

$$

Теперь мы складываем правые значения, у которых левые значения нечётны, что даёт нам

$$

Что, как можно легко убедиться, является результатом $$.

Разумеется, интересно то, почему эта загадочная процедура работает?

Если посмотреть в левую колонку, и пройтись до самого верха, записывая $$, когда мы увидим нечётное число и $$, когда встретим чётное, то получим $$, что является $$ в двоичной форме (и, конечно, это никакое не совпадение). На самом деле, это и есть стандартный алгоритм преобразования чисел в двоичную форму.

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

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

Это всё довольно мило, но примечательно то, что метод можно слегка преобразовать для выполнения гораздо более сложных вычислений, которые очень полезны в современной криптографии (с открытым ключом).

Возведение в степень методом русских крестьян

Мы внесём в алгоритм два небольших изменения; оба будут касаться только колонки $$.

• Вместо удвоения мы будем возводить в квадрат
• Вместо сложения в конце мы будем умножать.

Для каждой строки в таблице вместо умножения $$ на соответствующую степень $$ мы будем возводить его в соответствующую степень $$. Умножение всего этого даст нам $$.

Давайте посмотрим, как это будет работать с теми же значениями $$ и $$.

$$

Умножение соответствующих членов даёт

$$

Что на самом деле равно $$.

Но в отличие от умножения, такой метод не просто достаточно эффективен: он очень эффективен.

Если мы хотим найти $$ в степени $$, то мы можем сделать это, перемножив $$ раз число $$. Это как вычислять $$ сложением $$ раз числа $$: можно сделать и так, но если $$ больше $$, то потраченным временем можно распорядиться и с большей пользой.

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

Разумеется, для этого мы должны уметь умножать, но это нас устраивает: алгоритм умножения позволяет нам умножать удвоением и сложением, а адаптированная версия позволяет возводить в степень возведением в квадрат и умножением. Это выгодная сделка.

Краткое знакомство с RSA

Смысл этого в том, что способ реализации криптографии с открытым ключом RSA (Rivest-Shamir-Adleman) (и некоторые другие) подразумевает, что для шифрования и расшифровки сообщений нам нужно вычислять степени.

Процедура работает следующим образом: мы выбираем закрытую пару простых чисел $$ и $$, и сообщаем миру значение $$. (Значения $$ и $$ мы храним в секрете: алгоритм основан на том, что задача разложения $$ на множители сложна.)

Затем мы подбираем число $$ и находим $$ такое, что $$ на $$ больше, чем произведение $$. Мы сообщаем всему миру $$. (Число $$ мы храним в секрете. Алгоритм основан на том, что нахождение $$ без знания $$ и $$ является сложной задачей.)

Теперь мы представляем сообщение как целое число $$. Зашифрованная форма сообщения $$ является остатком от деления $$ на $$.

Благодаря магии теории чисел (на самом деле это не магия, а малая теорема Ферма) исходное сообщение будет являться остатком от деления $$ на $$.

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

И тут возникает одна проблема.

На практике значения $$ и по крайней мере или $$, или $$ очень велики. Если нам придётся выполнять повторное умножение, то Вселенная умрёт раньше, чем мы закончим. Этот алгоритм уменьшает объём работы до вполне приемлемых пропорций. Умножения $$ (или $$) сокращаютя до числа умножений, являющегося являющегося малым делителем числа разрядов $$ (или $$).

Но это не единственная проблема.

Значение $$ почти невероятно велико. Мы не сможем записать его, даже если бы использовали для хранения одной цифры каждую элементарную частицу в известной нам Вселенной. Как же это работает?

Ответом снова будет теория чисел. Одно из очень удобных свойств вычисления остатков заключается в том, что неважно, на каком этапе расчётов мы их находим. Если нам нужно узнать остаток от какой-то величины при делении на $$, то можно вычислить всё число и разделить его на $$, или, что гораздо логичнее, можно разбить всё на этапы и брать остаток, когда обрабатываемое значение превышает $$. В конце мы гарантированно получим тот же результат.

RSA русских крестьян

Итак, теперь мы видим, как вычислить зашифрованное сообщение. Можно использовать адаптированное умножение по методу русских крестьян, но теперь мы можем добавить последний штрих — когда квадрат числа превышает $$), мы будем брать остаток от деления на $$.

Давайте посмотрим, как это работает, на примере нахождения остатка от деления $$ на $$.

$$

Что даёт нам

$$

И это на самом деле (фух!) является остатком от деления $$ на $$.

Но вот неожиданная развязка. Это алгоритм вычисления степени, который обычно называется возведением в степень (повторяющимся) возведением в квадрат. И на самом деле этот алгоритм (или его небольшая вариация) используется в реализации криптографии с открытым ключом (например, в RSA), в которой применяется вычисление степеней.

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

Благодарности

На MathsJam Gathering 2017 Элен Смит и Линда Голденберг выступили с докладом о техниках умножения, в том числе о методе русских крестьян. Именно тогда до меня наконец дошло, что алгоритм повторного возведения в квадрат является адаптацией умножения русских крестьян, и я понял, что стоит поделиться этим осознанием с читателями. Через двадцать минут Оливер Мастерс рассказал о матрице Фибоначчи и упомянул алгоритм повторного возведения в квадрат для возведения в степень матрицы. К счастью, он не связал его с алгоритмом умножения. Ещё через пять минут Колин Райт (@ColinTheMathmo) подвёл итог докладам и упомянул об этой связи. Но к тому моменту я уже всё равно принял решение написать эту статью, что и сделал.