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

Вот умный способ вычислить 2⁷ на 33-часовом калькуляторе. Мы начинаем с перемножения 2: 2² = 4, 2³ = 8, 2⁴ = 16, 2⁵ = 32. Когда мы переходим к более высоким степеням 2, стрелка на циферблате движется дальше и дальше, и, когда мы возводим 2 в 6-ю степень, она совершает более чем оборот. Можно применить следующий небольшой трюк, из-за которого стрелка словно меняет направление движения, вместо того чтобы вращаться и дальше по часовой. Мы просто говорим, что 32 часа на нашем 33-часовом калькуляторе это –1 час. Потом, когда мы делаем два последующих умножения на 2, то получаем –4 часа, или 29 часов. Благодаря этому приему нам не требуется возводить 2 в 7-ю степень, что равно 128, и затем находить остаток при делении на 33. Для очень больших чисел подобный метод экономии неоценим для компьютерных вычислений, когда нужно сделать все как можно быстрее.

Рис. 4.17. Вычисление степеней 2 на 33-часовом калькуляторе

Но как мы можем быть уверены, что 29, закодированное число покупателя, надежно защищено? В конце концов, хакер может перехватить это число, когда оно путешествует по интернету. Также он может легко найти открытый ключ Боба, состоящий из 33-часового калькулятора и инструкции возвести номер кредитной карты в 7-ю степень. Все, что необходимо хакеру, чтобы взломать код, – найти число, 7-я степень которого, вычисленная на 33-часовом калькуляторе, равна 29.

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

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

Обобщение малой теоремы Ферма, найденное Эйлером, гарантирует существование магического декодирующего числа D. Боб может найти произведение D множителей, каждый из которых равен закодированному номеру кредитной карты, и восстановить исходный номер кредитной карты. Но вы можете определить число D, только если знаете секретные простые числа p и q. Знание этих простых чисел становится ключом к раскрытию кодов интернета, потому что вам требуется решить следующую задачу на секретном часовом калькуляторе:

E × D = 1 (modulo (p –  1) × (q – 1)).

Когда мы подставим наши числа, то придем к уравнению

7 × D = 1 (modulo 2 × 10).

Значит, вопрос состоит в нахождении числа, которое при умножении на 7 дает результат, который при делении на 20 дает остаток 1. D = 3 подойдет, потому что 7 × 3 = 21 = 1 (modulo 20).

И, если мы возведем закодированный номер кредитной карты в третью степень, вновь появится исходный номер:

29³ = 2 (modulo 33).

Возможность восстановления номера кредитной карты из закодированного сообщения зависит от знания секретных простых чисел p и q. Поэтому любому, кто захочет взломать коды из интернета, необходимо найти способ разложить число N на простые множители. Каждый раз, когда вы покупаете книгу онлайн или скачиваете музыкальный трек, вы используете магию простых чисел для защиты вашей кредитной карты.

Вопрос на миллион долларов

Те, кто придумывает коды, всегда стараются опережать взломщиков. Математики постоянно придумывают все более изощренные способы отправки секретных сообщений на случай, если когда-либо будет взломан код, основанный на простых числах. Для защиты траекторий полета самолетов уже используется новый вид кодирования, называемый эллиптической криптографией (для краткости ЭК). Приз в миллион долларов данной главы связан с пониманием математики эллиптических кривых, лежащих в основе этих новых кодов.

Существует множество различных эллиптических кривых, но все они описываются уравнениями вида y² = x³ + ax + b. Каждая кривая соответствует различным значениям a и b: например, а = 0 и b = –2 задают y² = x³ – 2.