|
|
Статьи Соросовского Образовательного журнала в текстовом формате
Статья посвящена некоторым понятиям теории эллиптических кривых - бурно развивающейся области современной математики с широчайшим диапазоном приложений - от криптографии до математической физики.
РАЦИОНАЛЬНЫЕ ТОЧКИНА ЭЛЛИПТИЧЕСКИХ КРИВЫХ
Ю. П. СОЛОВЬЕВ
Московский государственный университет
им. М.В. Ломоносова
Древний мир оставил нам в наследство несколько великих математических сочинений. Пожалуй, самое загадочное из них - это "Арифметика" Диофанта Александрийского в 13 книгах, созданная в середине III века н. э. Удивительна судьба "Арифметики" Диофанта. После пожара Александрийской библиотеки "Арифметика" исчезла более чем на тысячелетие и считалась полностью утраченной. Лишь в 1464 году немецкий ученый Региомонтан случайно обнаружил 6 из 13 книг "Арифметики". В первый раз она была напечатана в латинском переводе в 1575 году. После издания 1621 года, подготовленного Баше де Мезириаком, книга стала настольной для многих математиков, например П. Ферма (1601-1665) и Р. Декарта (1596-1650).
За тысячелетие книга совсем не устарела - она сильно опережала уровень лучших алгебраических исследований XVI века. Посудите сами: в отличие от европейских алгебраистов того времени Диофант свободно оперировал отрицательными и рациональными числами, владел буквенной нотацией для уравнений, а самое главное - умел находить решения в целых и рациональных числах линейных, квадратных, кубических уравнений и систем с двумя и более неизвестными с целыми коэффициентами. Решение таких уравнений - они называются диофантовыми - с тех пор находится в центре внимания математиков.
В статье речь пойдет о решении некоторых диофантовых уравнений, наиболее красивых и, кроме того, связанных живыми нитями с многими областями математики. Нам придется не только бросить пристальный взгляд на сочинения Диофанта, но и коснуться самых последних событий современной математической жизни.
МЕТОД СЕКУЩИХ ДИОФАНТА
Проиллюстрируем этот метод на конкретном примере - частном случае одного из тех уравнений, которые Диофант разбирает в своей "Арифметике". Пусть дано уравнение
x 2 - y 2 = 1
и требуется найти все его рациональные решения, то есть все пары
(x ; y) = (a / b; c / d), a, b, c, d k Z,
обращающие уравнение (1) в числовое тождество.
Уравнение (1), как и любое уравнение от переменных x, y, можно рассматривать как кривую на плоскости Oxy. В данном случае это гипербола (рис. 1). Сразу бросается в глаза решение (1, 0) - точка пересечения P кривой с осью Ox. Проведем через эту точку секущую
y = k(x - 1)
и найдем ее вторую точку пересечения с кривой (1). Для этого подставим выражение (2) для y в уравнение (1) и решим получившееся квадратное уравнение относительно x. Получим
Корень x1 = 1 нам и так известен (он относится к точке (1, 0)), а второй корень x2 = (k 2 + 1)/(k 2 - 1) дает искомую вторую точку
Для любого рационального k (k ? ? 1) эта формула определяет точку на нашей кривой, а значит, и рациональное решение данного уравнения. (При k = ? 1 секущая пересекает кривую только в точке P (см. рис. 1).) Обратно, для любого рационального решения, то есть рациональной точки M на кривой, секущая PM задается уравнением (2) с рациональным k (ибо тогда катеты прямоугольного треугольника PMH рациональны).
Таким образом, формула (3) при всевозможных рациональных k ? ? 1 дает все решения в рациональных числах уравнения (1).
Сам Диофант, конечно, не вводил в рассмотрение систему координат Oxy, не рассматривал кривую данного уравнения - метод координат появился лишь в работах Декарта в XVII веке. Диофант делал подстановку (2) чисто алгебраически и получил, разумеется в другой записи, формулу (3). Более того, он понимал, что продемонстрированный метод с успехом применим не только к многочлену x 2 - y 2 - 1, но и вообще к многочлену второй степени от двух переменных общего вида
p(x, y) = ax 2 + bxy + cy 2 + dx + ey + f,
где a, b, _, f - целые (или рациональные) числа при условии, что у многочлена удалось найти хотя бы один рациональный корень.
Не на всякой кривой второй степени имеются рациональные точки, например их нет на окружности x 2 + y 2 = 3 или на эллипсе x 2 + 82y 2 = 3 . Задача о существовании хотя бы одной рациональной точки на кривой второй степени оказалась очень трудной. Первые нетривиальные продвижения в ее решении получили индийские математики Брахмагупта (VII век) и Бхаскара (XII век), а окончательный ответ был найден лишь в 1768 году французским математиком Ж.-Л. Лагранжем (1736-1813).
Диофант не ограничился уравнениями второй степени. Он с успехом берется и за третью степень, демонстрируя общий прием на одной конкретной задаче.
ОДНА ЗАДАЧА ИЗ "АРИФМЕТИКИ" ДИОФАНТА. КАСАТЕЛЬНАЯ
В этой задаче требуется найти рациональное решение уравнения
y (6 - y) = x 3 - x.
Короткое решение, содержащее в зародыше замечательную идею, Диофант излагает с незаурядным мастерством. Попробуем, пишет он, замену x = 2y - 1 (разумеется, обозначения у него совсем другие). Тогда получим
6y - y 2 = 8y 3 - 12y 2 + 4y.
Если бы 6 равнялось 4, как хорошо бы сократились члены с y в первой степени! Но число 4 появилось из двойки при замене x = 2y - 1. Так заменим его тройкой, то есть возьмем x = 3y - 1. Тогда линейные члены сокращаются и остается
y 2(27y - 26) = 0,
откуда y = 26/27 и x = 17/9. Получено рациональное решение (17/9, 26/27) кубического уравнения (4).
На первый взгляд здесь нет ничего особенного - просто удачная замена x = 3y - 1 позволила найти решение. В чем же глубокая идея? Чтобы ответить на этот вопрос, вновь воспользуемся методом координат и построим график кривой (4) (рис. 2). На этом рисунке красным показана прямая x - 3y + 1 = 0. Она касается нашей кривой в точке P = (-1, 0) (действительно, уравнение (5) имеет кроме корня y = 26/27 еще и "два слившихся корня" y 2 = 0).
По этому пути можно было бы пойти дальше: через полученную рациональную точку (17/9, 26/27) провести еще одну касательную к кривой (4) до пересечения с ней в третьей рациональной точке и т. д. Но Диофант не сделал этого шага. И потребовалось более 1500 лет, прежде чем математики сумели до конца воспользоваться идеями Диофанта.
КРИВЫЕ ТРЕТЬЕЙ СТЕПЕНИ
Оставаясь верными геометрическому подходу, рассмотренному выше, сосредоточим внимание не на решении уравнений третьей степени, а на следующем эквивалентном вопросе: найти рациональные точки кривой на плоскости, задаваемой уравнением третьей степени
f (x, y) = ax 3 + bx 2y + _ + hx + iy + j = 0
с целыми коэффициентами.
Все такие кривые можно разбить на два больших класса. К первому классу отнесем те кривые, у которых имеются точки заострения (как точка (0, 0) кривой y 2 = x 3) или точки самопересечения (рис. 3, а), а также кривые, для которых f (x, y) представляется в виде
f (x, y) = f1(x, y) " f2(x, y),
где f1(x, y), f2(x, y) - многочлены меньших степеней (рис. 3, б ). Назовем такие кривые вырожденными. Второй класс образуют невырожденные кривые третьей степени с целыми коэффициентами - такие кривые называются эллиптическими. Именно этот (наиболее общий) класс и будет нас интересовать. Мы будем рассматривать эллиптические кривые, заданные в канонической форме, то есть уравнением
y 2 = x 3 + ax 2 + bx + c
с целыми коэффициентами a, b и c, в котором многочлен P(x) = x 3 + ax 2 + bx + c не имеет кратных корней.
Это не нарушает общности: любую неособую кривую f (u, u) = 0 третьей степени можно преобразованием вида x = r (u, u), y = s (u, u), где r (u, u) и s (u, u) - рациональные функции, привести к виду (6). При этом если коэффициенты многочлена f (x, y) целые, то задачу отыскания рациональных точек на кривой f (x, y) = 0 можно свести к аналогичной задаче для кривой (6) с целыми a, b и c.
ГРАФИЧЕСКОЕ ИЗОБРАЖЕНИЕ ЭЛЛИПТИЧЕСКИХ КРИВЫХ
Выясним, как выглядит кривая (6). Чтобы получить ее графическое изображение, нужно нарисовать график функции и симметрично отразить его относительно оси Ox. Для построения графика построим вначале график функции y = x 3 + ax 2 + bx + c. Известно, что у многочлена третьей степени (без кратных корней) может быть либо один, либо три вещественных корня. По предположению, все эти корни различны. Поэтому график y = x 3 + ax 2 + bx + + c выглядит так, как показано на рис. 4, а и б. А теперь уже нетрудно получить график функции (рис. 5, а) и тем самым вид эллиптической кривой y 2 = x 3 + ax 2 + bx + c (рис. 5, б ) для случая кривой, изображенной на рис. 4, а. Кривая, изображенная на рис. 4, б, исследуется аналогично; результирующая кривая состоит из двух кусков (см. рис. 7, б ).
Отметим следующее обстоятельство. Графики функций и склеиваются в точках x1 , x2 , x3 гладко, то есть без углов. Это происходит потому, что касательные к графику в точках x1 , x2 , x3 вертикальные. Другими словами, их угловой коэффициент обращается в бесконечность. Это легко доказать подсчетом производной функции .
СЛОЖЕНИЕ ТОЧЕК НА ЭЛЛИПТИЧЕСКОЙ КРИВОЙ
Метод секущих, примененный к эллиптической кривой С, приводит к неожиданному результату: оказывается, точки на ней можно складывать. Определим операцию сложения точек на С отправляясь от ее графического изображения (рис. 6). Возьмем на С две точки P и Q и проведем через них прямую. Эта прямая имеет третью точку пересечения с кривой C. Отразим эту точку от оси Ox и назовем получившуюся точку суммой точек P и Q (обозначение: P + Q, рис. 6). Не всегда прямая, проходящая через две точки, пересекает кривую C в третьей, например с вертикальной прямой этого не происходит. Далее мы более подробно рассмотрим эту ситуацию.
Исследуем свойства операции сложения точек на эллиптической кривой. За образец примем свойства операции сложения чисел. Эта операция коммутативна, то есть a + b = b + a, и ассоциативна, то есть (a + b) + c = a + (b + c). Кроме того, у этой операции существует нуль, то есть такое число 0, что a + 0 = a для любого а, и, наконец, для каждого числа а имеется противоположное ему, то есть такое число - a, что a + (- a) = 0.
А как обстоит дело на эллиптической кривой? Прежде всего операция сложения точек коммутативна. В самом деле, для вычисления Q + P мы используем ту же самую прямую, что и для P + Q, следовательно, P + Q = Q + P.
Ассоциативность для сложения точек на эллиптической кривой также выполняется, но геометрически доказать этот факт достаточно трудно. Проще всего ассоциативность можно получить с помощью приводимых ниже формул (8) и (9).
Займемся теперь существованием нуля. Нуль - это такая точка Е на кривой, что P + E = P. Как ее найти? Посмотрим на рис. 7, а. Пусть на кривой дана точка P. Мы хотим найти нечто такое, что если провести прямую через P и это нечто, пересечь получившуюся прямую с кривой, а потом отразить точку пересечения от оси Ox, то вновь получится P. Обозначим буквой R точку, симметричную P относительно оси Ox. Из сказанного вытекает, что прямая должна проходить через точки P и R, то есть должна быть вертикальной. Следовательно, если имеется точка Е, для которой P + E = P, то эта точка не может находиться в плоскости, поскольку она должна лежать и на кривой, и на любой вертикальной прямой.
Раз точки Е в плоскости нет, а она очень нужна, то добавим ее к плоскости (и, разумеется, к кривой) и назовем бесконечно удаленной точкой. Каким требованиям она должна удовлетворять? Любая вертикальная прямая стремится к бесконечности сверху и снизу. Потребуем, чтобы все эти точки в бесконечности были одной и той же точкой Е, то есть будем считать, что Е есть точка пересечения всех вертикалей. Это требование корректно определяет точку Е - нулевую точку относительно нашей операции сложения. В силу нашего соглашения вертикальная прямая, проходящая через точку P, проходит через P и Е. Поэтому точка R пересечения этой прямой с эллиптической кривой удовлетворяет соотношению P + R = E, то есть является противоположной к P. В то же время R - это точка, симметричная к P относительно оси Ox. Значит, любая точка P имеет противоположную -P = R. Тем самым мы убедились, что сложение точек на эллиптической кривой обладает теми же свойствами, что и сложение чисел.
Как вычислить точку P + P ? Когда точки были различны, мы проводили секущую. Раз они слились, понятно, что нужно провести касательную (рис. 7, б ). А что делать, чтобы найти 3P ? Очень просто, берем сумму 2P и P. Подобно этому, 4P = = 3P + P, 5P = 4P + P и т. д.
ПОИСК РАЦИОНАЛЬНЫХ ТОЧЕК
Вооружившись операцией сложения, займемся теперь рациональными точками. Пусть P = (x1 ; y1), Q = (x2 ; y2) - две рациональные точки на эллиптической кривой y 2 = x 3 + ax 2 + bx + c, где a, b, c - целые числа, и прямая, проходящая через P и Q, пересекает эту кривую еще в одной точке R = (x3 ; y3). Тогда R также является рациональной точкой.
Доказывается это утверждение довольно просто. Если
y = kx + d
есть уравнение прямой, проходящей через точки P и Q, то k и d - рациональные числа, поскольку их можно выразить через координаты (x1 ; y1) и (x2 ; y2) точек P и Q по формулам
Подставив (7) в уравнение эллиптической кривой, получим для x уравнение третьей степени с рациональными коэффициентами
(kx + d )2 = x 3 + ax 2 + bx + c,
то есть
x 3 + (a - k 2)x 2 + (b - 2kd )x + c - d 2 = 0.
По теореме Виета
x1 + x2 + x3 = k 2 - a.
Так как x1 и x2 рациональны, то рациональным будет x3 , а значит, и y3 = kx3 + d.
Из этого доказательства сразу же следует формула для вычисления координат точки P + Q. По определению, P + Q получается из R отражением от оси Ox, значит, координаты (u, u) точки P + Q можно найти по формулам
u = k 2 - a - x1 - x2 , u = - ku - d = - [k(u - x1) + y1].
Подставив сюда значение k, получим
Ясно, что, если x1 = x2 , эти формулы не имеют смысла. В этом случае уравнение секущей (7) нужно заменить уравнением касательной и действовать по прежней схеме. В результате получим
Таким образом, зная хотя бы одну рациональную точку P на эллиптической кривой, мы можем найти по указанным формулам точки 2P, 3P и т.д. Рассмотрим пример. Пусть кривая задана уравнением y 2 = x 3 - 2 и P = (3, 5). Тогда 2P = (129/100, - 383/1000) - новая рациональная точка. Теперь можно вычислить 3P, 4P и т. д. Заметим, что объем вычислений с каждым шагом стремительно растет. Если обозначить через un первую координату точки nP, то
Далее нарастание происходит еще быстрее. Например, у u11 в числителе 71 знак.
В настоящее время неизвестно никакой общей процедуры для нахождения всех рациональных решений уравнения y 2 = x 3 + ax 2 + bx + c. В разобранном примере y 2 = x 3 - 2 одно решение (3, 5) мы просто подобрали; в общем же случае неизвестно никакого метода, который позволил бы найти это первое решение. Нахождение рационального решения эллиптического уравнения с помощью эффективной процедуры является одной из крупнейших проблем теории чисел. Однако, если одно решение есть, можно найти другие по формулам (8) и (9).
ПОРЯДОК ТОЧЕК НА ЭЛЛИПТИЧЕСКОЙ КРИВОЙ
При получении точек nP из данной точки P возможны два случая. В первом случае на шаге n получается нуль, то есть существует такое число n, что nP = E. Если mP ? E для всех m < n, то говорят, что точка P имеет конечный порядок n. Например, на кривой y 2 = x 3 + 4 точка P = (0, 2) имеет порядок 3, на кривой y 2 = x 3 + 1 точка P = (2, 3) имеет порядок 6, на кривой y 2 = x 3 - 43x + 166 точка P = (3, 8) имеет порядок 7. Можно поставить вопрос: сколько существует рациональных точек конечного порядка и каковы эти порядки?
В 1976 году американский математик Б. Мазур получил выдающийся результат, показав, что если P - рациональная точка порядка n, то n # 10 или n = 12; к тому же на эллиптической кривой существует самое большее 16 рациональных точек конечного порядка.
Второй случай - это когда все точки 2P, 3P, 4P и т.д. различны. В 1901 году французский математик А. Пуанкаре (1854-1912) высказал гипотезу о том, что всегда можно найти такое конечное число рациональных точек P1 , _, Pr бесконечного порядка, что всякая рациональная точка P выражается через них, то есть представляется в виде
P = n1P1 + _ + nr Pr + Q,
где n1 , _, nr - целые числа, однозначно определяемые точкой P, а Q - точка конечного порядка. Сами же точки P1 , _, Pr не выражаются друг через друга. Число r называется рангом кривой.
Гипотезу Пуанкаре в 1922 году доказал английский математик Л. Морделл, но его доказательство не дает никакого способа для вычисления ранга. Лишь в 1995 году было показано, что ранг эллиптической кривой может быть найден с помощью весьма сложной аналитической конструкции.
В явном виде найдены лишь кривые, ранг которых не превосходит 21, при этом возникают гигантские числа. Например, кривая
y2 + xy = x3 - 431 092 980 766 333 677 958 362 095 891 166x +
+ 5 156 283 555 366 643 659 035 652 799 871 176 909 391 533 088 196
имеет ранг 20.
КОДЫ С ОТКРЫТЫМ КЛЮЧОМ
Около десяти лет назад эллиптические кривые получили неожиданное применение в теории кодирования - в так называемом кодировании с открытым ключом. Сущность его заключается в следующем. Прежде всего выбираются два больших простых числа, скажем p и q, каждое примерно длиной в 100-200 знаков. Затем составляется их произведение N = pq. Для того чтобы прочитать сообщение, ваш корреспондент должен знать лишь значение числа N. Однако, для того чтобы расшифровать сообщение, нужно найти множители p и q. Поэтому любые сообщения, переданные таким образом, будут расшифрованы лишь тогда, когда противник сможет разложить число N на множители. Насколько быстро это можно сделать? Ясно, что наименьший множитель числа N должен быть меньше . Поэтому можно использовать такую процедуру: сначала проверяется, делится ли число N на 2, затем на 3, на 5 и на все последующие простые числа, не превосходящие . Если число N невелико, эта процедура удобна, но для больших N она абсолютно неэффективна. Например, если число N имеет около 100 знаков и если каждую секунду проверять 1 000 000 возможных делителей, то понадобится 3,2 " 1037 лет для его разложения на множители. Поэтому нужна более эффективная процедура. В 1987 году голландский математик Х. Ленстра предложил быстрый алгоритм для разложения больших чисел на простые множители. Мы не имеем возможности привести его здесь, отметим лишь, что сердцевиной его является операция сложения точек на эллиптической кривой.
КРИВЫЕ ВЫСШИХ СТЕПЕНЕЙ
Мы ограничились здесь кривыми (а значит, диофантовыми уравнениями) степеней 2 и 3. А как обстоит дело со степенями n $ 4? В этом случае также естественно выделить класс невырожденных кривых степени n (типичный представитель - кривая x n + yn = 1). При n > 3 картина разительно меняется. Еще в 1931 году Л. Морделл выдвинул гипотезу: на таких кривых число рациональных точек всегда конечно. Гипотеза Морделла более полувека была в центре внимания ведущих математиков всего мира. В 1983 году ее доказал немецкий математик Г. Фальтингс. Эффективных алгоритмов для нахождения этих точек пока неизвестно.
РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА
1. Коблиц Н. Введение в эллиптические кривые и модулярные формы. М.: Мир, 1988.
2. Прасолов В. В., Соловьев Ю. П. Эллиптические функции и алгебраические уравнения. М.: Факториал, 1997.
3. Степанов С. А. Арифметика алгебраических кривых. М.: Наука, 1991.
4. Успенский В.А. Как теория чисел помогает в шифровальном деле // Соросовский Образовательный Журнал. 1996. ╧ 6. С. 122-127.
* * *
Юрий Петрович Соловьев, доктор физико-математических наук, профессор Московского государственного университета им. М.В. Ломоносова. Специалист в области дифференциальной геометрии, алгебраической и дифференциальной топологии, математической физики. Автор 60 научных статей, десяти монографий и учебников.
