(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 с двух различных перспектив. Для меня это образец умения рассматривать задачу с разных сторон.
Как использовать часы для отправки секретных сообщений через интернет
Мы теперь почти готовы показать, как эти часы применяются для обмена секретными сообщениями в интернете.
Когда вы покупаете что-либо на веб-сайте, номер кредитной карты кодируется вашим компьютером, который использует публичный часовой калькулятор данного веб-сайта. Итак, веб-сайт должен сообщить вашему компьютеру, сколько часов на его калькуляторе. Это первое из двух чисел, которые получает ваш компьютер. Давайте назовем его N. В нашем примере с веб-сайтом футболок, администратором которого был Боб, это число равнялось 126 619. Также для совершения вычисления вашему компьютеру требуется второе кодирующее число, которое мы назовем Е. Номер вашей кредитной карты C кодируется путем возведения его в степень Е, причем вычисления совершаются N-часовым калькулятором. Таким образом, получается закодированное число CE (modulo N), и именно его ваш компьютер посылает на веб-сайт.
Но как же веб-сайт декодирует это число? И снова магия простых чисел играет в этом ключевую роль. Давайте предположим, что N – простое число (позже мы увидим, что это не слишком подходит для надежного шифрования, зато данное предположение помогает понять, куда мы направляемся). Если мы перемножим числа CE достаточное количество раз, то чудесным образом снова появится число С. Но сколько множителей (D), каждый из которых представляет CE, мы должны взять? Другими словами, когда (CE)D = C на p-часовом калькуляторе?
Конечно, последнее равенство выполнится, если E × D = p. Но p – простое число, поэтому такого числа D не может быть. Однако если мы продолжим перемножать С, то найдется другая точка, где мы гарантированно получим в ответе С. В следующий раз номер кредитной карты появится, когда мы возведем его в степень 2(p – 1) + 1. Он появится снова при возведении в степень 3(p – 1) + 1. Значит, чтобы найти декодирующее число, нам необходимо найти такое D, что E × D = 1 (modulo (p – 1)). Такое уравнение значительно легче решить. Но проблема в том, что Е и p – открытые числа, поэтому хакер также может легко найти декодирующее число D. Для безопасной процедуры мы можем воспользоваться открытием, которое сделал Эйлер о часах, на которых p × q, a не просто p часовых делений (p и q – простые числа).
Если вы возьмете время С на циферблате, где имеется p × q часов, то через сколько шагов последовательность C, C × C, C × C × C, … начнет повторяться? Эйлер обнаружил, что это произойдет через (p – 1) × (q – 1) шагов. Итак, чтобы вернуться к первоначальному времени, нужно возвести C в степень (p – 1) × (q – 1) + 1, или k × (p – 1) × (q – 1) + 1, где k – число повторений последовательности.
Теперь мы знаем, что для того, чтобы декодировать сообщение CE на часах с p × q часовыми делениями, нам требуется найти такое декодирующее число D, что E × D = 1 (modulo (p – 1) × (q – 1)). Итак, нам необходимо делать вычисления на секретном часовом калькуляторе с (p – 1) × (q – 1) часами. Хакер знает только числа N и Е, и он должен найти секретные простые числа p и q, чтобы получить секретный часовый калькулятор. Следовательно, взлом кодов интернета сводится к разложению числа N на простые множители. А как мы видели в разделе о подкидывании монеты через интернет, это фактически невозможно, когда числа достаточно большие.
Давайте посмотрим на коды интернета в действии, но для очень небольших p и q. Тогда нам легко будет проследить за происходящим. Пусть Боб выбрал для своего веб-сайта футболок простые числа 3 и 11, так что открытый часовой калькулятор, с помощью которого покупатели кодируют номера своих кредитных карт, имеет 33 часа. Боб хранит в тайне простые числа 3 и 11, потому что они являются ключом к декодированию сообщений. Но Боб не делает секрета из числа 33, ведь это число часов на открытом часовом калькуляторе. Вторая порция информации, которая доступна на веб-сайте Боба, – кодирующее число Е. Пусть оно равно 7. Каждый, кто покупает футболку на веб-сайте Боба, делает одно и то же: возводит номер своей кредитной карты в 7-ю степень на 33-часовом калькуляторе.
Сайт Боба посещает покупатель, который был одним из самых первых получателей кредитных карт, и ее номер равен 2. Возведите 2 в 7-ю степень на 33-часовом калькуляторе, что равно 29.
Вот умный способ вычислить 27 на 33-часовом калькуляторе. Мы начинаем с перемножения 2: 22 = 4, 23 = 8, 24 = 16, 25 = 32. Когда мы переходим к более высоким степеням 2, стрелка на циферблате движется дальше и дальше, и, когда мы возводим 2 в 6-ю степень, она совершает более чем оборот. Можно применить следующий небольшой трюк, из-за которого стрелка словно меняет направление движения, вместо того чтобы вращаться и дальше по часовой. Мы просто говорим, что 32 часа на нашем 33-часовом калькуляторе это –1 час. Потом, когда мы делаем два последующих умножения на 2, то получаем –4 часа, или 29 часов. Благодаря этому приему нам не требуется возводить 2 в 7-ю степень, что равно 128, и затем находить остаток при делении на 33. Для очень больших чисел подобный метод экономии неоценим для компьютерных вычислений, когда нужно сделать все как можно быстрее.
Рис. 4.17. Вычисление степеней 2 на 33-часовом калькуляторе
