Тайны чисел: Математическая одиссея

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

Что такое часовой калькулятор?

Передовые коды, которые используются в интернете, на самом деле опираются на математическое изобретение, которому сотни лет, сделанному, когда никто и не мечтал об интернете. Я имею в виду часовой калькулятор. В следующем разделе мы узнаем, как часовые калькуляторы используются при кодировании в интернете, но сначала давайте познакомимся с принципом их работы. Сперва рассмотрим случай 12-часового циферблата. Мы все знакомы со сложением на таких часах – мы понимаем, что через четыре часа после 9 будет 1 час. Это то же самое, что сложение чисел с последующим нахождением остатка при делении суммы на 12. Данное действие можно записать так:

4 + 9 = 1 (modulo 12).

Мы пишем «modulo 12», потому что 12 – это модуль, точка, после которой числа стартуют снова. Мы можем находить подобные суммы и на часах с другим количеством часовых делений, не ограничиваясь двенадцатью. Так, в случае 10 часов на циферблате:

9 + 4 = 3 (modulo 10).

А как умножаются числа на часовом калькуляторе? Умножение сводится к прибавлению определенное количество раз. Например, 4 × 9 означает, что нужно взять четыре девятки и сложить их вместе. Где окажется стрелка на 12-часовом циферблате после сложения четырех девяток? 9 + 9 – то же самое, что 6 часов. Каждый раз, когда мы прибавляем последующую девятку, часовая стрелка движется назад на 3 часа. В конце она окажется на 12 часах. Поскольку 0 – крайне важное число в математике, мы далее будем называть это положение, которое заканчивает круг и начинает следующий, 0 часов. Итак, у нас получится странный на вид ответ:

4 × 9 = 0 (modulo 12).

А как будет происходить возведение какого-либо числа в степень? Давайте рассмотрим 9⁴, что означает перемножение четырех девяток. Мы только что научились делать модульное умножение, поэтому должны легко справиться и с этим. Поскольку числа становятся большими, будет легче взять остаток от деления на 12, чем следить за числами на часах. Начнем с 9 × 9, что равняется 81. Каков будет остаток при делении на 12, другими словами, чему соответствует 81 час на циферблате? Оказывается, остаток равен снова 9. Сколько бы мы ни перемножали 9, всякий раз мы опять придем к 9:

9 × 9 = 9 × 9 × 9 = 9 × 9 × 9 × 9 = 9⁴ = 9 (modulo 12).

Ответ на часовом калькуляторе можно получить, сделав вычисления на обычном калькуляторе и затем взяв остаток от деления на число часовых делений. Но сила часового калькулятора состоит в том, что часто вам вовсе не требуется совершать вычисление на обычном калькуляторе. Вы можете найти, чему равно 7⁹⁹, на 12-часовом калькуляторе? Подсказка: сначала вычислите 7 × 7, а потом снова умножьте результат на 7. Вы видите закономерность?

Ферма сделал фундаментальное открытие о вычислениях на калькуляторе, у которого имеется простое число часовых делений. Обозначим его, к примеру, p. Ферма обнаружил, что если вы возьмете какое-то число с циферблата и возведете его в степень p, то придете к тому же числу, с которого стартовали. Это утверждение сейчас называется малой теоремой Ферма, в отличие от его знаменитой Великой теоремы.

В таблице 4.13 приведены некоторые вычисления на калькуляторах с простым и составным числом часов.

Таблица 4.13

Поскольку число 5 – простое, при возведении 2 в пятую степень на 5-часовом калькуляторе получится снова 2. Итак, 2⁵ =2 (modulo 5). Магия будет гарантированно работать, если на калькуляторе простое число часов. Она может не удаться, если вы возьмете калькулятор с составным числом часов. Например, 6 – составное число, и на 6-часовом калькуляторе 2⁶оказывается равным не 2, а 4.

По мере того как стрелка перемещается по часам, начинает проступать закономерность. Поскольку после p – 1 шагов мы гарантированно возвращаемся в то место, с которого стартовали, последовательность начинает повторяться через p – 1 шаг. Порою последовательность повторяется несколько раз на протяжении p – 1 шагов. Вот что мы увидим на циферблате с 13 часами, когда будем возводить 3 в последовательные степени 3¹, 3² и так далее вплоть до 3¹³:

3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3.