Книга: Тайны чисел: Математическая одиссея
Назад: Почему разложение чисел означает взлом кода?
Дальше: Как использовать часы для отправки секретных сообщений через интернет
Что такое часовой калькулятор?
Передовые коды, которые используются в интернете, на самом деле опираются на математическое изобретение, которому сотни лет, сделанному, когда никто и не мечтал об интернете. Я имею в виду часовой калькулятор. В следующем разделе мы узнаем, как часовые калькуляторы используются при кодировании в интернете, но сначала давайте познакомимся с принципом их работы. Сперва рассмотрим случай 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).
А как будет происходить возведение какого-либо числа в степень? Давайте рассмотрим 94, что означает перемножение четырех девяток. Мы только что научились делать модульное умножение, поэтому должны легко справиться и с этим. Поскольку числа становятся большими, будет легче взять остаток от деления на 12, чем следить за числами на часах. Начнем с 9 × 9, что равняется 81. Каков будет остаток при делении на 12, другими словами, чему соответствует 81 час на циферблате? Оказывается, остаток равен снова 9. Сколько бы мы ни перемножали 9, всякий раз мы опять придем к 9:
9 × 9 = 9 × 9 × 9 = 9 × 9 × 9 × 9 = 94 = 9 (modulo 12).
Ответ на часовом калькуляторе можно получить, сделав вычисления на обычном калькуляторе и затем взяв остаток от деления на число часовых делений. Но сила часового калькулятора состоит в том, что часто вам вовсе не требуется совершать вычисление на обычном калькуляторе. Вы можете найти, чему равно 799, на 12-часовом калькуляторе? Подсказка: сначала вычислите 7 × 7, а потом снова умножьте результат на 7. Вы видите закономерность?
Ферма сделал фундаментальное открытие о вычислениях на калькуляторе, у которого имеется простое число часовых делений. Обозначим его, к примеру, p. Ферма обнаружил, что если вы возьмете какое-то число с циферблата и возведете его в степень p, то придете к тому же числу, с которого стартовали. Это утверждение сейчас называется малой теоремой Ферма, в отличие от его знаменитой Великой теоремы.
В таблице 4.13 приведены некоторые вычисления на калькуляторах с простым и составным числом часов.
Таблица 4.13
Поскольку число 5 – простое, при возведении 2 в пятую степень на 5-часовом калькуляторе получится снова 2. Итак, 25 =2 (modulo 5). Магия будет гарантированно работать, если на калькуляторе простое число часов. Она может не удаться, если вы возьмете калькулятор с составным числом часов. Например, 6 – составное число, и на 6-часовом калькуляторе 26оказывается равным не 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.
Стрелка не посещает все деления на часах, тем не менее по-прежнему имеется повторяющаяся закономерность, которая приводит стрелку назад к 3 часам после перемножения тринадцати троек.
Мы уже сталкивались с похожей математикой в главе 3, когда рассматривали жульнический прием совершенных тасовок в покере. Там мы варьировали число карт в колоде и задавались вопросом, сколько совершенных тасовок необходимо сделать, чтобы карты возвратились к первоначальному расположению. В колоде с 2N картами порою необходимо выполнить все 2N – 2 совершенных тасовок, но бывает, их требуется сделать значительно меньше. Если в колоде 52 карты, то после всего лишь 8 совершенных тасовок они вернутся к исходному расположению. Но колода с 54 картами требует 52 совершенных тасовок.
Ферма никогда не излагал в полной мере свои рассуждения, поэтому он оставил в виде задания для будущих поколений математиков объяснение своего открытия, что магия всегда срабатывает для часов с простым числом делений. В конечном счете доказательство было найдено Леонардом Эйлером.
Малая теорема Ферма
Ниже приведено объяснение малой теоремы Ферма. Теорема утверждает, что в случае циферблата с простым числом p часовых деленийAp = A (modulo p).
Для понимания доказательства нужны усилия, но не специальные знания: чтобы вы могли проследить его, требуется лишь сосредоточенность.В качестве первого шага рассмотрим простой случай. Если A = 0, то теорема верна, потому что сколько бы раз мы ни умножили 0 на себя, все равно получится 0. Поэтому давайте предположим, что А не равно нулю. Мы намереваемся показать, что произведение p – 1 множителя А равно 1. Этого достаточно для доказательства теоремы, поскольку умножение 1 на А возвратит нас к А.Теперь давайте составим список всех часов на циферблате за исключением 0. В этом списке p – 1 элемент:1, 2, …, p – 1.
Теперь умножим каждое число в этом списке на А и получимА × 1, А × 2, …, А × (p – 1) (modulo p).
Позвольте мне показать, что часы в этом списке будут теми же, что и в первоначальном списке 1, 2, …, p – 1, хотя они будут расположены в другом порядке. Если бы это было не так, то либо одно из произведений равнялось бы 0, либо какие-то два произведения были равны друг другу. Не может произойти что-либо другое, поскольку на циферблате имеется лишь p часов.Предположим, что А × n и А × m дают один и тот же ответ на нашем p-часовом циферблате, где n и m лежат между 1 и p – 1 (я покажу, почему это означает, что n = m). Итак, А × n – А × m = А × (n – m) равно нулю на часовом калькуляторе, то есть А × (n – m) на обычном калькуляторе делится на p.Ключевым в следующем шаге доказательства будет использование того факта, что p – простое число. Подобно химической молекуле, число А × (n – m) построено из произведения атомов (простых чисел), составляющих А, и простых чисел, составляющих n – m. Но число p – простое, атом арифметики, и его нельзя расщепить далее. Поскольку А × (n – m) делится на p, это число должно быть одним из атомов, использованных при построении А × (n – m), ведь каждое число однозначно разлагается на простые множители. Но А не делится на p без остатка, поэтому p должно входить в список атомов, использованных при построении n – m. Другими словами, n – m делится на p. Но что это означает? Это означает, что n и m соответствуют одному и тому же времени на нашем p-часовом циферблате. Вы можете использовать схожую аргументацию, чтобы показать, что А × n не может быть нулем часов, если ни А, ни n не равны нулю часов.Заметьте, что крайне важно то, что на циферблате простое число часов. Мы уже видели, что 4 × 9 равняется нулю на 12-часовом калькуляторе, хотя ни 4, ни 9 не равно нулю.Теперь у нас есть два списка – 1, 2, …, p – 1 и А × 1, А × 2, …, А × (p – 1), – составленные из одних и тех же чисел, хотя и расположенных в разном порядке. Теперь мы можем воспользоваться эффектным трюком, который, вероятно, открыл сам Ферма. Если мы перемножим все числа в каждом из списков, то получим один и тот же ответ, потому что порядок перемножения не имеет значения. Первый список даст нам 1 × 2 × … × (p – 1), что мы можем записать как (p – 1)!. Второй список приводит к p – 1 множителю А и опять-таки произведению чисел от 1 до p – 1. После небольшой перестановки мы можем переписать это как (p – 1)!× Аp – 1. И эти два ответа равны на нашем часовом калькуляторе:(p – 1)! = (p – 1)! × Аp – 1 (modulo p).
Из этого следует, что (p – 1)! × (1 – Аp – 1) делится на p, и мы можем использовать тот же трюк, что и ранее. Никакое из чисел 1, 2, …, p – 1 не делится на p, значит, (p – 1)! не может делиться на p. Единственная возможность состоит в том, что 1 – Аp – 1 делится на p. А это приводит к тому, что вычисление Аp – 1 на часовом калькуляторе всегда будет давать ответ 1 – предложением объяснить данный результат Ферма и раззадорил математиков.В этой аргументации есть несколько интересных ингредиентов. Разумеется, немаловажно то обстоятельство, что если A × B делится без остатка на простое число p, то либо А, либо B должно также делиться на данное простое число. Это следует из специального свойства простых чисел. Но мне представляется красивым взгляд на список 1, 2, …, p – 1 с двух различных перспектив. Для меня это образец умения рассматривать задачу с разных сторон.
Назад: Почему разложение чисел означает взлом кода?
Дальше: Как использовать часы для отправки секретных сообщений через интернет
