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

Графіки кривих y² = x³ − x та y² = x³ − x + 1

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

Рівняння еліптичної кривої над дійсними числами можна спростити до вигляду (називається рівнянням Вейєрштрасса):

${\displaystyle y^{2}=x^{3}+ax+b~}$,

де ${\displaystyle a}$ і ${\displaystyle b}$ — дійсні числа.

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

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

не дорівнює нулю. Хоч коефіцієнт -16 не впливає на визначення того, чи має крива особливі точки, але він використовується при більш глибокому вивчені еліптичних кривих.

Графік кривої без особливих точок складається з двох частин, якщо її дискримінант додатний, та з однієї — якщо від'ємний. Наприклад, для графіків на рисунку в першому випадку дискримінант дорівнює ${\displaystyle 64}$, а в другому — ${\displaystyle -368}$.

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

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

При роботі в проективному просторі можна побудувати групову структуру на будь-якій кубічній кривій. Крива, яка задовольняє рівняння у вигляді Вейєрштрасса, матиме точку на нескінченності ${\displaystyle O}$ з однорідними координатами ${\displaystyle (0:1:0)}$, яка буде нейтральним елементом в групі.

Оскільки крива симетрична відносно осі абсцис, то для будь-якої скінченної точки ${\displaystyle P}$ протилежною до неї точку ${\displaystyle -P}$ можна визначити як симетричну точку відносно осі абсцис. Для ${\displaystyle O}$ буде ${\displaystyle -O=O}$.

Якщо ${\displaystyle P}$ та ${\displaystyle Q}$ — дві точки на кривій, то ми можемо однозначно описати третю точку ${\displaystyle P+Q}$ наступним чином: спочатку проведемо пряму через точки ${\displaystyle P}$ та ${\displaystyle Q}$. Ця пряма перетне криву також у третій точці ${\displaystyle R}$. Далі візьмемо ${\displaystyle P+Q}$ рівною ${\displaystyle -R}$.

Отримане визначення додавання точок працює за винятком кількох спеціальних випадків, пов'язаних з точкою на нескінченності та кратністю перетину. Далі визначимо ${\displaystyle P+O=P=O+P}$. Це робить ${\displaystyle O}$ нейтральним елементом групи. Потім, якщо ${\displaystyle P}$ та ${\displaystyle Q}$ протилежні, то визначимо ${\displaystyle P+Q=O}$. У випадку, коли ${\displaystyle P=Q}$ буде тільки одна точка, через яку проведемо дотичну до кривої. У більшості випадків дотична буде перетинати криву у другій точці ${\displaystyle R}$, візьмемо її як протилежну до ${\displaystyle 2P}$. Однак, якщо ${\displaystyle P}$ буде точкою перегину, то за ${\displaystyle R}$ візьмемо ${\displaystyle P}$, і в цьому випадку буде ${\displaystyle 2P=O}$.

Для кубічної кривої, яка не задовольняє рівняння у вигляді Вейєрштрасса, все ще можна побудувати групову структуру, визначивши одну з дев'яти точок перегину як нейтральний елемент ${\displaystyle O}$. У проективній площині кожна пряма перетинає криву у трьох точках з урахуванням кратності. Для точки ${\displaystyle P}$ протилежна їй ${\displaystyle -P}$ визначається як третя точка на прямій, що проходить через ${\displaystyle O}$ та ${\displaystyle P}$. Тоді для будь-яких точок ${\displaystyle P}$ та ${\displaystyle Q}$ сума ${\displaystyle P+Q}$ визначається як ${\displaystyle -R}$, де ${\displaystyle R}$ є третьою з точок, у яких пряма, що проходить через ${\displaystyle P}$ та ${\displaystyle Q}$, перетинає криву.

Нехай ${\displaystyle K}$ - поле, над яким визначається еліптична крива, позначимо цю криву через ${\displaystyle E}$. Тоді ${\displaystyle K}$-раціональні точки ${\displaystyle E}$ - це точки на ${\displaystyle E}$, координати яких з ${\displaystyle K}$, та містять точку на нескінченності. Отримана множина ${\displaystyle K}$-раціональних точок позначається через ${\displaystyle E(K)}$. Вона також утворює групу, оскільки властивості алгебричних рівнянь показують, що якщо ${\displaystyle P}$ знаходиться в ${\displaystyle E(K)}$, то і ${\displaystyle -P}$ також є в ${\displaystyle E(K)}$, та якщо принаймні дві точки з трьох ${\displaystyle P}$, ${\displaystyle Q}$ і ${\displaystyle R}$ містяться в ${\displaystyle E(K)}$, то і третя теж. Крім того, якщо ${\displaystyle K}$ є підполем ${\displaystyle L}$, то ${\displaystyle E(K)}$ є підгрупою ${\displaystyle E(L)}$.

Вищеописану групу можна визначити як алгебраїчно, так і геометрично. Нехай крива задовольняє рівняння ${\displaystyle y^{2}=x^{3}+ax+b}$ над полем ${\displaystyle K}$ (характеристика якого не рівна 2, 3), точки ${\displaystyle P=(x_{P},y_{P})}$ та ${\displaystyle Q=(x_{Q},y_{Q})}$ лежать на цій кривій. Спочатку розглянемо випадок, коли ${\displaystyle x_{P}\neq x_{Q}}$ (перший рисунок нижче). Нехай ${\displaystyle y=sx+d}$ — пряма, що проходить через P і Q, тоді вона матиме такий кутовий коефіцієнт:

${\displaystyle s={\frac {y_{P}-y_{Q}}{x_{P}-x_{Q}}}~}$

Оскільки ${\displaystyle K}$ — поле, то ${\displaystyle s}$ визначений. Рівняння прямої та рівняння кривої мають однакові значення ${\displaystyle y}$ у точках ${\displaystyle x_{P}}$, ${\displaystyle x_{Q}}$ та ${\displaystyle x_{R}}$.

${\displaystyle (sx+d)^{2}=x^{3}+ax+b~}$

яке еквівалентне ${\displaystyle 0=x^{3}-s^{2}x^{2}-2sdx+ax+b-d^{2}}$. Ми знаємо, що це рівняння має корені ${\displaystyle x_{P}}$, ${\displaystyle x_{Q}}$ та ${\displaystyle x_{R}}$. Запишемо

${\displaystyle (x-x_{P})(x-x_{Q})(x-x_{R})=x^{3}-(x_{P}+x_{Q}+x_{R})x^{2}+(x_{P}x_{Q}+x_{P}x_{R}+x_{Q}x_{R})x-x_{P}x_{Q}x_{R}~}$

З прирівняння коефіцієнтів при ${\displaystyle x^{2}}$ та з рівняння прямої через дві точки знаходимо значення ${\displaystyle x_{R}}$ та ${\displaystyle y_{R}}$. Таким чином отримаємо ${\displaystyle R=(x_{R},y_{R})=-(P+Q)}$, де

${\displaystyle x_{R}=s^{2}-x_{P}-x_{Q}~}$,

${\displaystyle y_{R}=-y_{P}+s(x_{P}-x_{R})~}$.

Якщо ${\displaystyle x_{P}=x_{Q}}$, то існує два варіанти:

1) ${\displaystyle y_{P}=-y_{Q}}$ (третій та четвертий рисунки нижче), включаючи випадок, коли ${\displaystyle y_{P}=y_{Q}=0}$ (четвертий рисунок), тоді сума точок ${\displaystyle P}$ та ${\displaystyle Q}$ дорівнюватиме ${\displaystyle O}$. Таким чином протилежною до кожної точки є точка симетрична відносно осі ${\displaystyle Ox}$.

2) ${\displaystyle y_{P}=y_{Q}\neq 0}$, тоді ${\displaystyle Q=P}$ та ${\displaystyle R=(x_{R},y_{R})=-(P+P)=-2P=-2Q}$ (другий рисунок) знаходиться наступним чином:

${\displaystyle s={\frac {3x_{P}^{2}+a}{2y_{P}}}}$,

${\displaystyle x_{R}=s^{2}-2x_{P}}$,

${\displaystyle y_{R}=y_{P}+s(x_{R}-x_{P})}$.

Формулювання еліптичних кривих як вкладення тора в комплексну проективну площину випливає безпосередньо з властивості еліптичних функцій Вейєрштрасса. Ці функції і їх перші похідні пов'язані формулою:

${\displaystyle \wp '(z)^{2}=4\wp (z)^{3}-g_{2}\wp (z)-g_{3}}$.

Тут ${\displaystyle g_{2}}$ і ${\displaystyle g_{3}}$ — константи; ${\displaystyle \wp (z)}$ — еліптична функція Вейєрштрасса, а ${\displaystyle \wp '(z)}$ — її похідна. Видно, що співвідношення—у вигляді еліптичної кривої (над комплексними числами). Функції Вейерштрасса двічі періодичні; тобто, вони є періодичними у відношенні ґратки ${\displaystyle \Lambda .}$ По суті, функції Вейєрштрасса натурально визначені на торі ${\displaystyle T=\mathbb {C} /\Lambda }$. Цей тор може бути вкладений в комплексну проектну площину відображенням

${\displaystyle z\to (1,\wp (z)\wp '(z))}$.

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

Класи ізоморфізму можна розглянути простішим способом. Константи ${\displaystyle g_{2}}$ і ${\displaystyle g_{3}}$, що називаються модулярними інваріантами, єдиним чином визначені структурою тора. Втім, комплексні числа є полем розкладу для многочленів, а значить, еліптичні криві можна записати як

${\displaystyle y^{2}=x(x-1)(x-\lambda )}$.

Можна показати, що

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

і

${\displaystyle g_{3}={\frac {1}{27}}(\lambda +1)(2\lambda ^{2}-5\lambda +2)}$,

отже модулярний дискримінат рівний

${\displaystyle \Delta =g_{2}^{3}-27g_{3}^{2}=\lambda ^{2}(\lambda -1)^{2}}$.

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

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

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

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

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

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

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

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

${\displaystyle y^{2}=x^{3}-px-q}$,

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

${\displaystyle y^{2}=4x^{3}+b_{2}x^{2}+b_{4}x+b_{6}~}$,

де ${\displaystyle b_{2}}$, ${\displaystyle b_{4}}$, ${\displaystyle b_{6}}$ — константи, і поліном праворуч має тільки прості корені (позначення обрано з історичних причин). У полі характеристики 2 багато чого неможливо, тому загальне рівняння залишається без змін

${\displaystyle y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6}~}$

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

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

Множина скінченних точок еліптичної кривої y² = x³ − x над скінченним полем F₆₁.

Нехай ${\displaystyle K=\mathbb {F} _{q}}$ скінченне поле з ${\displaystyle q}$ елементів та ${\displaystyle E}$ еліптична крива визначена над ${\displaystyle K}$. Точну кількість раціональних точок еліптичної кривої ${\displaystyle E}$ над ${\displaystyle K}$ взагалі досить важко обчислити. Теорема Гассе про еліптичні криві дає, враховуючи точку на нескінченності, таку оцінку:

${\displaystyle |\#E(K)-(q+1)|\leq 2{\sqrt {q}}}$

Іншими словами, кількість точок кривої зростає приблизно так само як кількість елементів у полі.

Множина скінченних точок еліптичної кривої y² = x³ − x над скінченним полем F₇₁.

Множина точок ${\displaystyle E(\mathbb {F} _{q})}$ — скінченна абелева група. Вона завжди циклічна або ізоморфна прямій сумі двох циклічних груп. [2] Наприклад,[3] крива, визначена рівнянням ${\displaystyle y^{2}=x^{3}-x}$, над полем ${\displaystyle \mathbb {F} _{71}}$ має 72 точки (71 скінченних точок враховуючи ${\displaystyle (0,0)}$ та одна точка на нескінченності) та ізоморфна ${\displaystyle \mathbb {Z} _{2}\oplus \mathbb {Z} _{36}}$. Кількість точок на певній кривій можна обчислити через алгоритм Шуфа.

Вивчення кривої над розширеннями поля ${\displaystyle \mathbb {F} _{q}}$ полегшується введенням локальної дзета-функції для ${\displaystyle E(\mathbb {F} _{q})}$, визначеної наступним чином

${\displaystyle Z(E(K),T)\equiv \exp \left(\sum _{n=1}^{\infty }\#\left[E(K_{n})\right]{T^{n} \over n}\right)}$,

де поле ${\displaystyle K_{n}}$ — це (з точністю до ізоморфізму) розширення поля ${\displaystyle K=\mathbb {F} _{q}}$ степеня n (тобто ${\displaystyle \mathbb {F} _{q^{n}}}$). Ця дзета-функція є раціональною функцією від T. Існує ціле число ${\displaystyle a}$ таке, що

${\displaystyle Z(E(K),T)={\frac {1-aT+qT^{2}}{(1-T)(1-qT)}}}$

Крім того,

${\displaystyle {\begin{aligned}Z\left(E(K),{\frac {1}{qT}}\right)&=Z(E(K),T),\\1-aT+qT^{2}&=(1-\alpha T)(1-\beta T),\end{aligned}}}$

де ${\displaystyle \alpha ,\beta \in \mathbb {C} }$ і ${\displaystyle |\alpha |=|\beta |={\sqrt {q}}}$. Цей результат є окремим випадком гіпотез Вейля. Наприклад,[4] дзета-функція для ${\displaystyle E:y^{2}+y=x^{3}}$ над полем ${\displaystyle F_{2}}$ дорівнює

${\displaystyle {\frac {1+2T^{2}}{(1-T)(1-2T)}}}$

це випливає з того, що

${\displaystyle \left|E(\mathbf {F} _{2^{r}})\right|={\begin{cases}2^{r}+1&r=2k-1\\2^{r}+1-2(-2)^{\frac {r}{2}}&r=2k\end{cases}},k\in \mathbb {N} ~}$.

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

З 1998 року використовування еліптичних кривих для розв'язування криптографічних завдань, таких як цифровий підпис, було закріплено у стандартах США ANSI X9.62 та FIPS 186–2. В Україні ухвалений стандарт цифрового підпису базується на еліптичних кривих ДСТУ 4145-2002[5].

• Н. Коблиц (2001). Курс теории чисел и криптографии = A Course in Number Theory and Cryptography. Научное издательство «ТВП». ISBN 5-85484-014-6.
• Н. Коблиц (2000). Введение в эллиптические кривые и модулярные формы = Introduction to Elliptic Curves and Modular Forms. ИО НФМИ. ISBN 5-8032-3325-0.
• С. Ленг (2000). Эллиптические функции = Elliptic functions. ИО НФМИ. ISBN 5-8032-3326-9.
• Joseph H. Silverman (1986). The Arithmetic of Elliptic Curves. Springer. ISBN 0-387-96203-4.
• Lawrence Washington (2003). Elliptic Curves: Number Theory and Cryptography. Chapman & Hall/CRC. ISBN 1-58488-365-0.