Тайны чисел. Математическая одиссея - Маркус Дю Сотой

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

Существует множество различных эллиптических кривых, но все они описываются уравнениями вида 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 записывается в виде десятичного числа, дробная часть которого уходит в бесконечность без появления повторяющейся последовательности:

√6 = 2,449489742783178…

Вопрос на миллион долларов связан с нахождением точек на этой кривой, где и 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 будут дробями: