Викия

Математика

Эллиптическая кривая

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Элипти́ческая крива́я — это множество точек, удовлетворяющих уравнению

y2 + a1xy + a3y = x3 + a2x2 + a4x + a6.

Если характеристика поля (Char K), над которым рассматривается данное уравнение, \neq 2, 3 \!, то уравнение с помощью замены координат приводится к канонической форме (форме Вейерштрасса):

y2 = x3 + ax + b.

Если Char K=3, то каноническим видом уравнения является вид

y2 = x3 + a2x2 + a4x + a6.

А если Char K=2, то уравнение приводится одному из видов:

y2 + cy = x3 + ax + b

или

y2 + xy = x3 + ax2 + b.

Эллиптические кривые являются одним из основных направлений в современной теории чисел. Например, они были использованы Эндрю Уайлзом (совместно Ричардом Тейлором) в доказательстве Великой теоремы Ферма. Они примененяются в криптографии (см. Криптография, основанная на эллиптических кривых). В частности, на эллиптических кривых основан российский стандат цифровой подписи ‎ГОСТ Р 34.10-2001. Кроме того, эллиптические кривые применяются при факторизации (см. Алгоритм Ленстры).

Эллиптическая кривая вовсе не то же самое, что эллипс: см. эллиптический интеграл о происхождении термина.

Эллиптические кривые над действительными числами Править

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

Считаем, что характеристика поля — не 2 и 3. Тогда эллиптическая кривая — плоская кривая, определённая уравнением вида

y^2 = x^3 + ax + b,

где a и b — действительные числа. Этот вид уравнений называется уравнениями Вейерштрасса.

Например, на следующем чертеже показаны эллиптические кривые, определённые уравнениями y^2 = x^3 - x и y^2 = x^3 - x + 1. Файл:ECexamples01.png

По определению, необходимо, чтобы такая кривая не имела особых точек. Геометрически это значит, что график не должен иметь точек возврата и самопересечений. Алгебраически это значит, что дискриминант

\Delta = -16(4a^3 + 27b^2)

не должен быть равен нулю.

Если кривая не имеет особых точек, то её график имеет две части, если дискриминант положителен, и одну — если отрицателен. Например, для графиков выше в первом случае дискриминант равен 64, а во втором он равен −368.

Групповой закон Править

Добавив «несобственную точку», мы получим проективный вариант этой кривой. Если P и Q — две точки на кривой, то мы можем единственным образом описать третью точку — точку пересечения данной кривой с прямой, проведённой через P и Q. Если прямая является касательной к кривой в точке, то такая точка считается дважды. Если прямая параллельна оси Oy, третьей точкой будет несобственная точка (точка, удалённая в бесконечность).

Файл:ECClines.svg

Тогда мы можем ввести групповую операцию «+» на прямой со следующими свойствами: положим, что несобственная точка является нулём группы; и если прямая пересекает данную кривую в точках P, Q и R, то необходимо, чтобы P + Q + R = 0 в группе. Можно показать, что таким образом кривая превращается в абелеву группу, то есть, в абелево многообразие. Можно также показать, что множество K-рациональных точек (включая несобственную) образует подгруппу этой группы. Если кривую обозначить E, то такая подгруппа обычно обозначается как E(K).

Описанная группа может быть описана и алгебраически. Пусть дана кривая y² = x³ − pxq над полем K (чья характеристика не равна ни 2, ни 3), и точки P = (xP, yP) и Q = (xQ, yQ) на кривой, допустим, что xPxQ. Пусть s = (yPyQ)/(xPxQ); так как K — поле, то s чётко определено. Тогда мы можем определить R = P + Q = (xR, yR) следующим образом:

x_R = s^2 - x_P - x_Q,
y_R = -y_P + s(x_P - x_R).

Если xP = xQ, то у нас два варианта: если yP = −yQ, то сумма определена как 0; значит, обратную точку к любой точке на кривой можно найти, отразив её по оси Ox. Если yP = yQ ≠ 0, то R = P + P = 2P = (xR, yR) определяется так:

s = {(3{x_P}^2 - p)}/{(2y_P)},
x_R = s^2 - 2x_P,
y_R = -y_P + s(x_P - x_R).

Если yP = yQ = 0, то P + P = 0.

Эллиптические кривые над полем комплексных чисел Править

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

\wp'(z)^2 = 4\wp(z)^3 -g_2\wp(z) - g_3.

Здесь g_2 и g_3 — константы; \wp(z)эллиптическая функция Вейерштрасса, а \wp'(z) — её производная. Видно, что соотношение — в виде эллиптической кривой (над комплексными числами). Функции Вейерштрасса дважды периодичны; то есть, они являются периодом в отношении структуры Λ по сути, функции Вейерштрасса натурально определены на торе T=\mathbb{C}/\Lambda. Этот тор может быть вложен в комплексную проективную плоскость отображением

z\to (1,\wp(z), \wp'(z)).

Это отображение — групповой изоморфизм, отображающий структуру натуральной группы тора в проективную плоскость. Кроме того, это изоморфизм поверхностей Римана, то есть, топологически, данную эллиптическую кривую можно рассмотреть как тор. Если структура Λ связана со структурой cΛ умножением на ненулевое комплексное число c, то соответствующие кривые изоморфны. Классы изоморфизма эллиптических кривых определены j-инвариантом.

Классы изоморфизма можно рассмотреть более простым способом. Константы g_2 и g_3, называемые модулярными инвариантами, единственным образом определены структурой тора. Впрочем, комплексные числа являются полем разложения для многочленов, а значит, эллиптические кривые можно записать как

y^2=x(x-1)(x-\lambda).

Можно показать, что

g_2 = \frac{4^{1/3}}{3} (\lambda^2-\lambda+1)

и

g_3=\frac{1}{27} (\lambda+1)(2\lambda^2-5\lambda+2),

так что дискриминант модуляра равен

\Delta = g_2^3-27g_3^2 = \lambda^2(\lambda-1)^2.

Здесь λ иногда называют лямбда-функцией модуляра.

Отметим, что теорема об униформации утверждает, что любая компактная поверхность Римана рода 1 может быть представлена в виде тора.

Эллиптические кривые над произвольным полем Править

Эллиптические кривые могут быть определены над любым полем K; формально, эллиптическая кривая определяется как невырожденная проективная алгебраическая кривая над K с родом 1 с данной точкой, определённой над K.

Если характеристика поля K не равна 2 или 3, то любая эллиптическая кривая над K может быть записана в виде

y² = x³ − pxq,

где p и q — такие элементы K, что многочлен x³ − pxq (правая сторона) не имеет кратных корней. (Если характеристика равна 2 или 3, то необходимо ввести ещё несколько условий.)

Можно взять кривую как множество всех точек (x; y), которые удовлетворяют вышеуказанному уравнению, а x и y одновременно являются элементами алгебраического замыкания поля K. Точки кривой, обе координаты которых принадлежат K, называются K-рациональными точками.

Связь с теорией чисел Править

Теорема Морделла-Вейля утверждает, что если поле K — поле рациональных чисел (или, вообще, поле чисел), то группа K-рациональных точек — конечно порождённая. Это означает, что группа может быть выражена как прямая сумма свободной абелевой группы и конечной подгруппы кручения. Хотя и относительно легко определить подгруппу кручения E(K), но нет общего алгоритма для вычисления ранга свободной подгруппы. Формула для вычисления ранга даётся в гипотезе Бирча и Свиннертона-Дайера.

Недавнее доказательство Великой теоремы Ферма было сделано с помощью доказательства особого случая теоремы Таниямы — Шимуры, относящей эллиптические кривые над рациональными числами к модулярным формам; эта теорема недавно была доказана и в целом.

Точное число рациональных точек эллиптической кривой E над конечным полем Fp достаточно трудно вычислить, но теорема Хассе об эллиптических кривых утверждает, что

 \left| \sharp E( \mathbb{F}_p ) - p - 1 \right| < 2 \sqrt{p} .

Этот факт можно истолковать и доказать с помощью некоторых общих тем; см. Локальная дзета-функция, Этальная когомология. Число точек на данной кривой может быть вычислено с помощью алгоритма Шуфа.

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

Алгоритмы, использующие эллиптические кривые Править

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

Список литературы Править

  • Н. Коблиц Курс теории чисел и криптографии = A Course in Number Theory and Cryptography. — Москва: Научное издательство "ТВП", 2001. — С. 254. ISBN 5-85484-014-6
  • Н. Коблиц Введение в эллиптические кривые и модулярные формы = Introduction to Elliptic Curves and Modular Forms. — Новокузнецк: ИО НФМИ, 2000. — С. 312. ISBN 5-80323-325-0
  • С. Ленг Эллиптические функции = Elliptic functions. — Новокузнецк: ИО НФМИ, 2000. — С. 312. ISBN 5-80323-326-9
  • Joseph H. Silverman The Arithmetic of Elliptic Curves. — New York: Springer, 1986. — С. 402. ISBN 0-387-96203-4


Внешние ссылки Править

sv:Elliptisk kurva

Викия-сеть

Случайная вики