Еліптична крива

Еліптична крива над полем K - це множина точок проективної площини над K, що задовольняють рівнянню

$y^2+a_1 xy+a_3 y=x^3+a_2 x^2+a_4 x+a_6 ~$

разом з точкою на нескінченності.

Еліптичні криві є одним з основних об'єктів вивчення в сучасній теорії чисел і криптографії. Наприклад, вони були використані Ендрю Вайлзом (спільно з Річардом Тейлором) в доведенні Великої теореми Ферма. Еліптична криптографія є самостійним розділом криптографії, що присвячений вивченню криптосистем на базі еліптичних кривих. Зокрема, на еліптичних кривих заснований російський стандарт цифрового підпису . Еліптичні криві також застосовуються в деяких алгоритмах факторизації (наприклад Алгоритм Ленстри) і тестування простоти чисел.

Термін «еліптична крива» походить від терміну «еліптичний інтеграл».

Канонічна форма

Якщо характеристика поля K ($\operatorname{Char} K$) не рівна $2$ або $3$, то рівняння за допомогою заміни координат приводиться до канонічної форми (форми Вейерштраса):

$y^2=x^3+ax+b ~$.

Якщо $\operatorname{Char} K=3$, то канонічним видом рівняння є:

$y^2=x^3+a_2 x^2+a_4 x+a_6 ~$.

А якщо $\operatorname{Char} K=2$, то рівняння приводиться до одного з видів:

$y^2+y=x^3+ax+b~$ — суперсингулярні криві

або

$y^2+xy=x^3+ax^2+b~$ — несуперсингулярні криві.

Еліптичні криві над дійсними числами

Формальне визначення еліптичної кривої важке для розуміння і вимагає деяких знань з алгебричної геометрії. Спробуємо описати деякі властивості еліптичних кривих над полем дійсних чисел, використовуючи тільки знання алгебри і геометрії старших класів школи.

Вважаємо, що характеристика поля — не 2 і 3. Тоді еліптична крива — плоска крива, визначена рівнянням вигляду

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

де a і b — дійсні числа. Цей вид рівнянь називається рівняннями Вейерштрасса.

Наприклад, на наступному кресленні показані еліптичні криві, визначені рівняннями $y^2 = x^3 - x~$ і $y^2 = x^3 - x + 1~$.

За визначенням, необхідно, щоб така крива не мала особливих точок. Геометрично це значить, що графік не повинен мати точок повернення і перетинів. Алгебрично це означає, що дискримінант

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

не повинен бути рівний нулю.

Якщо крива не має особливих точок, то її графік має дві частини, якщо дискримінант додатний, і одну — якщо від'ємний. Наприклад, для графіків вище в першому випадку дискримінант рівний 64, а в другому він рівний -368.

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

Додавши «невласну точку», ми одержимо проективний варіант цієї кривої. Якщо $P~$ і $Q~$ — дві точки на кривій, то ми можемо єдиним чином описати третю точку — точку перетину даної кривої з прямою, проведеною через точки $P$ і $Q$. Якщо пряма є дотичною до кривої в точці, то точка рахується двічі. Якщо пряма паралельна осі $Oy$, третьою точкою буде невласна точка (точка на нескінченності).

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

Ця група може бути описана і алгебрично. Нехай задані крива $y^2=x^3-px-q$ над полем $K$ (характеристика якого не рівна ні 2, ні 3), і точки $P=(x_P,y_P)$ і $Q=(x_Q,y_Q)$ на кривій, допустимо, що $x_P\ne x_Q$. Хай $s=\frac{y_P-y_Q}{x_P-x_Q}~$; оскільки $K$ - поле, то $s$ чітко визначено. Тоді ми можемо визначити $R=P+Q=(x_R,y_R)~$ таким чином:

$x_R = s^2 - x_P - x_Q~$,

$y_R = -y_P + s(x_P - x_R)~$.

Якщо $x_P=x_Q$, то у нас два варіанти: якщо $y_P=-y_Q$, то сума визначена як 0; значить, обернену точку до будь-якої точки на кривій можна знайти, через її симетричне відображення по осі $Ox$. Якщо $y_P=y_Q\ne 0$, то $R=P+P=2P=(x_R,y_R)$ визначається так:

$s = \frac{3x_P^2 - p}{2y_P}\,$,

$x_R = s^2 - 2x_P\,$,

$y_R = -y_P + s(x_P - x_R)\,$.

Якщо $y_P=y_Q=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)$ — її похідна. Видно, що співвідношення—у вигляді еліптичної кривої (над комплексними числами). Функції Вейерштрасса двічі періодичні; тобто, вони є періодичними у відношенні ґратки $\Lambda.$ По суті, функції Вейєрштрасса натурально визначені на торі $T=\mathbb{C}/\Lambda$. Цей тор може бути вкладений в комплексну проектну площину відображенням

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

Це відображення — груповий ізоморфізм, що відображає структуру натуральної групи тора в проективну площину. Крім того, це ізоморфізм поверхонь Рімана, тобто, топологічно, дану еліптичну криву можна розглянути як тор. Якщо ґратка $\Lambda$ пов'язана із ґраткою $c\Lambda$ множенням на ненульове комплексне число $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$.

Тут λ іноді називають лямбда-функцією модуляра.

Еліптичні криві над довільним полем

Еліптичні криві можуть бути визначені над довільним полем $K$; формально, еліптична крива визначається як невироджена проектна алгебрична крива над $K$ з родом 1 з заданою точкою, визначеною над $K$.

Якщо характеристика поля $K$ не рівна 2 або 3, то будь-яка еліптична крива над $K$ може бути записана у вигляді

$y^2=x^3-px-q$,

де $p$ і $q$ — такі елементи $K$, що многочлен $x^3-px-q$ (права сторона) не має кратного кореня. (Якщо характеристика рівна 2 або 3, то необхідно ввести ще декілька умов.)

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

Зв'язок з теорією чисел

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

Недавнє доведення Великої теореми Ферма було зроблено за допомогою доведення особливого випадку теореми Таніями—Шимури, про зв'язок еліптичних кривих над раціональними числами з модулярними формами; ця теорема згодом була доведена і в цілому.

Точне число раціональних точок еліптичної кривої $E$ над скінченним полем $\mathbb{F}_p$ достатньо важко обчислити, але теорема Хассе стверджує, що

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

Число точок на даній кривій може бути обчислено за допомогою алгоритма Шуфа.

Застосування

Еліптичні криві над скінченними полями використовуються в деяких криптографічних застосуваннях і факторізації. Зазвичай, основна ідея, закладена в цих додатках, полягає в тому, що відомий алгоритм, що використовується для конкретних скінченних груп переписується для використання на групах раціональних точок еліптичних кривих.

Еліптична крива над скінченним полем

Еліптична крива $E(F_2^m)$ над скінченним полем $F_2^m$ є множина пар (x,y) елементів цього поля, що задовольняють афінне рівняння еліптичної кривої в нормальній формі Веєрштраса

$y^2+xy=x^3+Ax^2+B$

де $A,B \in F_2^m$ , $B\ne \;0$, разом із приєднаною нескінченною віддаленою точкою О. Пара (x,y) елементів основного поля називається афінними координатами точки еліптичної кривої. Нескінченно віддалена точка О не має афінних координат. Елементи А, В основного поля називаються коефіцієнтами рівняння еліптичної кривої. Число точок еліптичної кривої разом з нескінченною точкою називається порядком еліптичної кривої.

Поряд з афінними координатами точки також існують проективні координати. Класичне рівняння Веєрштраса для таких координат має вигляд:

$y^2z+xyz=x^3+Ax^2z+Bz^3$

а точками проективної еліптичної кривої є трійки елементів основного поля (x:y:z).

При додаванні точок еліптичної кривої, як результат ми отримуємо іншу точку цієї кривої. Правила додавання точок еліптичної кривої в афінних координатах можна записати таким чином:
1. $P+O=O+P$ для всіх $P \in E(F_2^m)$
2. Якщо $P(x,y) \in E(F_2^m)$, тоді $(x,y)+(x,x+y)=O$. Точка (x,x+y) позначається як –P і називається мінус P, точка –P також є точкою даної еліптичної кривої.
3. Якщо $P=(x1,y1)\in E(F_2^m)$
$Q=(x2,y2)\in E(F_2^m)$
де $P\ne \;\pm \;Q$
тоді $P+Q=(x3,y3)$ де

$x_3=(\frac{y_1+y_2}{x_1+x_2})^2+(\frac{y_1+y_2}{x_1+x_2})+x_1+x_2+A$
$x_3=(\frac{y_1+y_2}{x_1+x_2})(x_1+x_3)+x_3+y_1$

Геометричну ілюстрацію додавання можна побачити на рис. 1.1

Рис 1.1. Геометрична ілюстрація додавання точок на еліптичній кривій

4. Якщо $P=Q$, $P=(x1,y1)$ ,$P \in E(F_2^m)$, $P \ne \;-P$, тоді $2P= (x3,y3)$ , де
$x_3=x_1^2+\frac{B}{x_1^2}$
$y_3=x_1^2+(x_1+\frac{y_1}{x_1})x_3+x_3$

Геометричну ілюстрацію подвоєння можна побачити на рис. 1.2

Рис 1.2. Геометрична ілюстрація подвоєння

У даному огляді не приводиться огляд додавання в проективних координатах. Для переходу від афінних до проективних координат і навпаки існують відповідні формули трансформації.

Література

• Н. Коблиц Курс теории чисел и криптографии = 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-8032-3325-0
• С. Ленг Эллиптические функции = Elliptic functions. — Новокузнецк: ИО НФМИ, 2000. — С. 312. — ISBN 5-8032-3326-9
• Joseph H. Silverman The Arithmetic of Elliptic Curves. — New York: Springer, 1986. — С. 402. — ISBN 0-387-96203-4