Криптографические приключения. Таинственные шифры и математические задачи - Роман Душкин

Такими вопросами отец всегда сбивал меня с толку. Проблема была в том, что отец пользовался совершенно другими терминами, чем те, что употребляются в школе. Мне часто было не понятно, что он имеет в виду, хотя потом оказывалось, что я ответил бы на вопрос, если бы только он задал его правильными словами. Однако вмешалась Катя:

— Если одно целое число поделить на другое целое число, то в результате получится частное и остаток. Так?

Отец согласился и записал на листке формулу:

M/N=Q, ост. P ↔ M=N*Q+P

Это было понятно. Остаток всегда меньше делителя или равен нулю, если делимое делится на делитель нацело. Отец продолжил:

— Теперь давайте изучим так называемую «модульную арифметику», или, по-другому, «арифметику остатков». Она простая, если помнить несложные правила. Самое главное правило: два целых числа равны по некоторому модулю, если остатки от деления каждого из них на этот модуль равны:

M1/N=Q1, ост. P, M2/N=Q2, ост. P ↔ M1=M2 (mod N)

— При этом нас не интересуют полученные частные. Мы будем интересоваться только остатками. Это понятно?

Я кивнул, Катя тоже. Тут действительно всё было понятно. Тем временем отец продолжал:

— Эта специальная арифметика имеет интересное свойство. Если зафиксировать делитель, для которого мы вычисляем остатки, то получается, что результаты всех операций не превышают этот делитель. Ну то есть если выбранный делитель — это число N, то все результаты любых операций будут находиться в интервале от 0 до N — 1. Что это значит?

Я больше не мог сдержаться:

— Папа, рассказывай всё от начала и до конца. Не надо спрашивать: «Что это значит» и всё такое. Нам в школе про такое не рассказывали.

— Хорошо. Тогда слушайте внимательно. Это очень важная тема. Если что-то перестаёте понимать, останавливайте меня и сразу задавайте вопросы.

Мы кивнули, и отец продолжил:

— Что ж. Поскольку у нас результаты всех операций всегда будут находиться в интервале от 0 до N — 1, при этом все такие результаты будут целыми числами, то при сложении и вычитании чисел друг из друга по заданному модулю будет происходить циклический переход. У нас получится как будто бы кольцо. Ну вот представьте себе циферблат старых часов, где стрелки ходят по кругу. Только давайте договоримся, что на месте числа 12 находится 0. Тогда это будет арифметика по какому модулю? Кирилл?

— Очевидно, 12.

— Правильно. Давайте потренируемся складывать и вычитать в этой арифметике.

Отец начал задавать нам задачи. Сперва простые:

1 + 2, 2 + 3, 7 + 4…

Потом сложнее:

7 + 5, 9 + 8, 10 + 11…

Но всё оказалось просто. Чтобы сложить два числа, надо было стрелку установить на первое, а потом перемотать её по ходу часов на столько шагов, сколько составляло второе число. Поэтому 7 + 5 = 0 (mod 12), 9 + 8 = 5 (mod 12), а 10 + 11 = 9 (mod 12). Я спросил:

— А как быть, если хочешь в этой арифметике сложить большие числа, например, 1739 и 3412?

Однако и это было несложно. Ведь каждое целое число в этой арифметике равно своему остатку от деления на модуль. То есть в нашем примере число 1739 = 11 (mod 12), а число 3412 = 4 (mod 12). Так что с такими большими числами нужно действовать чуть сложнее, но всё равно просто: 1739 + 3412 (mod 12) = 11 + 4 (mod 12) = 3 (mod 12).

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

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

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

После этого отец продолжил:

— Это всё были приготовления. Теперь давайте вернёмся к проблеме, которую мы обсуждали в самом начале занятия. Есть задача секретного распределения ключей. Как с ней справиться? На помощь приходит модульная арифметика. Давайте рассмотрим пример. Возьмём модуль 13 и посмотрим, чему равны по этому модулю все степени числа 2 от нулевой до двадцатой. Кирилл, выпиши эти степени.

Я записал в блокноте: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576.

Теперь мы с Катей погрузились в расчёты и начали выписывать, чему равны эти числа по модулю 13. Хорошо, что папа был не против того, чтобы мы пользовались калькулятором. Получился такой ряд: 1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1, 2, 4, 8, 3, 6, 12, 11, 9. В общем-то сразу была видна закономерность. А отец спросил:

— Катерина, ты можешь сказать, чему будет равно 2 в степени 21 по модулю 13?

— Пять?

— Верно. Как вы видите, тут имеется явная закономерность — степени двойки вразнобой пробегают все числа от 1 до 12 при вычислении их остатка по модулю 13, потом всё повторяется. Этот период и эта последовательность будут повторяться до бесконечности. И это очень важное свойство, ради которого мы всё это рассмотрели. Давайте запишем такое уравнение:

2X = 11 (mod 13)

Отец написал его на листке и продемонстрировал нам. Неизвестное стояло в степени двойки, и я как-то сразу затруднился, поскольку в школе мы подобного ещё не проходили. Судя по виду Кати, она тоже не знала, как его решать. Отец же продолжил:

— Надо найти наименьшее число X, при подстановке которого в это уравнение оно становится правильным. Очевидно, что в данном случае это число 7. Но как решается это уравнение? Проблема в том, что решить его мы можем только способом перебора или очень сложного алгоритма, называющегося «дискретным логарифмированием». А теперь подумаем, что будет, если мы возьмём не модуль 13, а какое-нибудь другое число, состоящее из нескольких тысяч цифр. Теоретически такое уравнение решить можно, но на практике для этого потребуется слишком много времени. Очень много. Больше, чем есть у кого бы то ни было.