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

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

Это уравнение определяет кривую, которую я могу нарисовать на миллиметровке, как показано ниже, путем нахождения последовательности точек (x, y). Я ввожу значение х, рассчитываю выражение x³ – 2 и беру из него квадратный корень, чтобы найти соответствующее значение y. Так, если x = 3, мы получим x³ – 2 = 27 – 2 = 25. Чтобы получить y, мне нужно взять квадратный корень из 25, поскольку y² = x³ – 2. Итак, y равен 5 или –5 (потому что минус при умножении на минус дает плюс, всегда имеется два квадратных корня). Получившийся график симметричен относительно горизонтальной оси, потому что у каждого квадратного корня выше ее есть зеркальный отрицательный корень. Пока мы нашли две точки: (3, 5) и (3, –5).

Рис. 4.18. График эллиптической кривой

Эти точки на эллиптической кривой особенно приятны, потому что и х, и у являются целыми числами. Можете ли вы найти другие такие точки? Давайте попробуем подставить x = 2. Тогда x³ – 2 = 8–2 = 6, так что y = √6 или – √6. В первом примере у 25 был целочисленный квадратный корень, но квадратный корень из 6 не так хорош. Древние греки доказали, что не существует дроби (не говоря уже о целом числе), которая при возведении в квадрат дает 6. √6 записывается в виде десятичного числа, дробная часть которого уходит в бесконечность без появления повторяющейся последовательности:

Вопрос на миллион долларов связан с нахождением точек на этой кривой, где и x, и y являются целыми числами или дробями. В большинстве случаев такого не происходит, потому что, когда вы подставляете х, получающееся y не будет целым числом или даже дробью, потому что у большинства чисел нет красивого квадратного корня. Нам повезло найти красивые точки (3, 5) и (3, –5) на кривой, но будут ли другие такие точки?

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

Рис. 4.19. Как найти другие точки на эллиптической кривой, координаты которых будут дробями

Например, если мы проведем касательную к эллиптической кривой y² = x³ – 2 в точке (x, y) = (3, 5), то найдем, что она пересекает кривую в новой точке (x, y) = (129/100, 383/1000), где обе координаты являются дробями. Мы можем провести касательную и в новой точке, в результате получится еще одна точка, где х и y будут дробями:

Без этого геометрического построения было бы нелегко обнаружить, что подстановка дроби

приведет к у, который также будет дробью.

В данном случае мы можем повторять проведение касательных и получить на эллиптической кривой бесконечно много точек с координатами (x, y), задаваемыми дробями. Если вы нашли такую точку (x₁, y₁) на эллиптической кривой общего вида y² = x³ – ax + b, то подстановка

и

даст вам другую точку на кривой, где x₂ и y₂ также будут дробями.

Эта процедура генерирует для нашей кривой y² = x³ – 2 бесконечно много точек с координатами, являющимися дробями. Но есть такие эллиптические кривые, для которых невозможно получить бесконечно много точек с этим свойством. Рассмотрите, например, кривую, задаваемую уравнением

Оказывается, что на этой кривой имеется лишь конечное число точек, у которых x и y являются целыми числами или дробями:

Фактически у всех этих точек целочисленные координаты. Применение геометрического построения или алгебраической подстановки для получения других точек с дробными координатами лишь снова выдаст одну из этих шести точек.

Вопрос на миллион долларов, называемый гипотезой Бёрча – Свиннертон-Дайера, состоит в том, возможно ли сказать, на какой эллиптической кривой будет бесконечно много точек, обе координаты которых являются целыми числами либо дробями.

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

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