Если, напротив, х = 1, получим y² = 0, то есть у — 0. Подставим в уравнение х = —1.
Правая часть будет равна (—1)3—2 (—1) + 1 = —1 + 2 + 1 = 2, уравнение примет вид y² = 2. Его решениями будут у = √2 и у = —√2. Таким образом, точки с координатами (—1, √2) и (—1, —√2) также будут лежать на кривой. Эти решения не являются целыми, но это не важно — чтобы изобразить кривую на плоскости, нужно учесть все вещественные решения.
Эллиптическая кривая, заданная уравнением y² = х3-2х + 1.
Теперь выберем две точки Р и Q, лежащие на кривой, и соединим их прямой линией. Будем предполагать, что Р и Q несимметричны относительно оси абсцисс,
98
чтобы соединяющая их прямая не располагалась вертикально. Эта прямая пересечет кривую в точке, которую мы обозначим через PQ. Результатом операции над точками Р и Q будет точка Р + Q, симметричная PQ относительно оси абсцисс.
Результат операции сложения для точек P и Q эллиптической кривой.
Необходимо уточнить несколько моментов. Во-первых, прямая, проходящая через точки Р = (x1, y1) и Q = (х2, у2), пересекает кривую в некоторой третьей точке.
Так как мы предположили, что эта прямая не располагается вертикально, ее уравнение будет иметь вид у = mх + n, где m и n — вещественные числа. Подставив это выражение в уравнение нашей эллиптической кривой, получим:
(mx + n)² = x3 +ax+b.
Путем элементарных преобразований это уравнение можно привести к виду:
х3-Ах² + Вх + С = 0, (**)
где A = m², В = a — 2mn, С = b — n². Следовательно, теперь нам нужно вычислить корни многочлена третьей степени с вещественными коэффициентами. Два корня уже известны: это абсциссы x1 и х2 точек Р и Q, так как обе эти точки одновременно лежат и на кривой, и на прямой. Используем следующую лемму.
Лемма. Если многочлен третьей степени с вещественными коэффициентами имеет два вещественных корня, то третий корень многочлена также будет вещественным.
99
Докажем лемму. Пусть
Р(х) = x3 + Rx² + Sx + Т
многочлен третьей степени с вещественными коэффициентами. Обозначим его корни через x1, х2, х3. Следовательно, Р(х) можно представить в виде
Р(х) = (х - x1) (х - х2) (х - х3).
Выразим коэффициенты многочлена через его корни:
Р(х) = x3 — (х1 +x2 +х3)х² +(x1 x2 +x1 x3 +x2 x3)х — x1 x2x3.
К примеру, — R = x1 + х2 + х3. Чтобы получить третий корень многочлена, нужно вычесть —R из первых двух. По условию, и коэффициент R, и корни x1 и х2 — вещественные числа, следовательно, x3 также будет вещественным числом.
По лемме, которую мы только что доказали, существует вещественное число х3, которое удовлетворяет уравнению (**).
Подставив это число в равенство у = mx + n, получим координату у3 точки PQ. Осталось найти координаты симметричной ей точки — для этого заменим ординату на противоположную. Результатом операции над точками (x1, y1) и (х2, у2) будет точка (х3, —у3).
Мы показали, что точки Р = (0, 1) и Q = (1, 0) принадлежат эллиптической кривой y² = x3 —2х + 1. Вычислим координаты точки Р + Q. Для этого сначала нужно найти уравнение прямой, проходящей через Р и Q. Несложно показать, что эта прямая задается уравнением у = —х + 1. Получим уравнение:
(—х +1) 2 = x3 —2х +1 ↔ х²—2х + 1 = x3 —2х + 1 ↔ х² = x3 ↔ х² (х — 1) = 0.
Решениями этого уравнения будут х = 0 (дважды) и х = 1. Так как x1= 0 и х2 = 1, искомой точкой будет x3 = 0.
Подставив это значение в уравнение у = —х + 1, получим у = 1.
Таким образом, результатом операции над Р и Q будет точка Р + Q с координатами (0, —1).
Заметим, что в этом случае результатом операции над двумя целочисленными решениями уравнения вновь будет целочисленное решение.
В общем случае это верно тогда, когда коэффициенты уравнения являются целыми числами. Доказательство этого утверждения, по сути, ничем не отличается от доказательства приведенной выше леммы.
Мы преодолели первое препятствие: мы показали, что если прямая проходит через две несимметричные точки эллиптической кривой, то она также пересечет кривую в третьей точке. Но что произойдет, если точки Р и Q симметричны?
100
Они будут иметь координаты Р = (x1, y2) и Q = (х1—у2), а соединяющая их вертикальная линия будет задаваться уравнением х = х1 Подставив в уравнение эллиптической кривой х = x1 получим у² = х13 + ах1+b. Мы исключили переменную х и получили, что y² равно вещественному числу. Это уравнение имеет всего два решения, ух и — yv следовательно, прямая, соединяющая Р и Q, не будет пересекать эллиптическую кривую ни в одной другой точке. PQ не существует! Как же справиться с этой проблемой? Решение подскажут художники Возрождения, которые изобрели перспективу. Чтобы сделать свои полотна более реалистичными, они изображали параллельные прямые сходящимися в удаленной точке, называемой точкой схода. Последуем примеру художников и будем считать, что наша вертикальная прямая пересекает эллиптическую кривую в третьей точке О, расположенной на бесконечности. Эта точка будет играть роль точки схода.
Фреска «Троица» работы Мазаччо (1401-1428) — первого художника эпохи Возрождения, который использовал в своих работах математические законы перспективы, чтобы придать им ощущение глубины.
101
Точка О будет иметь реальный математический смысл, если мы введем третью переменную z так, что уравнение эллиптической кривой примет вид y²z = x3 + axz² + bz3.
Теперь все члены уравнения имеют третью степень. Это в некотором смысле означает, что отличить тройку (х, у, z) от любой из кратных ей ненулевых троек (Λх, Λy, Λz) невозможно: если мы подставим эти значения в уравнение, то всегда сможем сократить общий множитель Λ3. Мы получили координаты, которые называются однородными и обозначаются (х: у: z), чтобы указать, что две точки, которые на первый взгляд кажутся различными, как, например (1: 2: 3) и (2: 4: 6), в действительности совпадают, так как имеют кратные координаты. Можно предполагать, что координата z принимает только значения 0 и 1. При z = 1 уравнение кривой примет вид y² = x3 + ах + b и мы получим те же самые точки, которые рассматривали вначале. При z = 0 имеем x3 = 0, следовательно, х также равен 0. Так как три координаты не могут быть равны нулю одновременно, у должен быть отличным от нуля. Однако все точки вида (0: у: 0) равны, так как имеют кратные координаты, следовательно, можно предположить, что у — 1. Имеем новую точку (0:1: 0), которая не принадлежит кривой y² = x3 + ах + b. Это и будет наша точка О!
Подведем итог: сначала мы доказали, что любая прямая, не расположенная вертикально и проходящая через две точки эллиптической кривой, также пересечет кривую в третьей точке. Теперь, введя бесконечно удаленную точку, мы показали, что это же утверждение верно и для вертикальной прямой. Следовательно, можно определить операцию над любыми несовпадающими точками Р и Q. Но что, если эти точки совпадают? Начнем с того, что рассмотрим две различные точки Р и Q и будем постепенно приближать точку Q к точке Р. Прямые, соединяющие Р и Q, также будут смещаться. Пределом этих прямых будет касательная к кривой, которая в окрестностях точки Р не будет пересекать кривую ни в одной другой точке.
Касательная к кривой в точке P.
102
Когда точки Р и Q будут совпадать, будем рассматривать не прямую, соединяющую Р и Q, а касательную к кривой в точке Р. Путем аналогичных рассуждений можно показать, что эта прямая пересечет кривую в другой точке РР. Найдя точку, симметричную РР относительно оси абсцисс, получим искомый результат операции
Р + Р = 2Р.
Осталось прояснить одну небольшую тонкость: так как мы добавили к нашей кривой точку О, необходимо определить, каким будет результат операции над О и произвольной точкой кривой. Когда мы работаем с однородными координатами, точка О имеет тот же статус, что и все прочие точки кривой, следовательно, мы можем провести прямую, проходящую через О и Р, и повторить описанные выше рассуждения. При этом неизменно будет выполняться равенство О + Р = Р, таким образом, О — нейтральный элемент для определенной нами операции над точками эллиптической кривой.
Итак, мы определили операцию, которая любой паре точек кривой (совпадающих или нет) ставит в соответствие третью точку. Докажем, что эта операция является групповой. Мы уже указали, что О — нейтральный элемент группы. Определить точку, обратную точке Р, очень просто: эта точка (обозначим ее Р') будет симметрична ей относительно оси абсцисс, так как прямая, соединяющая Р и Р', расположена вертикально, следовательно, пересекает кривую в точку О, и Р + Р' = О.
Чтобы показать, что эта операция действительно определяет группу на множестве решений уравнения y² = x3 + ах + b, осталось доказать, что она обладает свойством ассоциативности.
