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

Приклади еліптичних кривих над дійсними числами, визначених рівняннями вигляду y² = x³ + a x + b, на області [-3,3]². Крива при a = b = 0 не еліптична.

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

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

разом з точкою на нескінченності та не містить особливих точок.

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

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

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

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

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

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

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

де $a$ і $b$ — дійсні числа.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$(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}~$

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

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

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

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

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

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

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

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

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

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

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

$\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$-раціональних точок є скінченно породженою. Це означає, що група може бути виражена як пряма сума вільної абелевої групи і скінченної підгрупи кручення. Хоч і відносно легко визначити підгрупу кручення $E(K)$, але немає загального алгоритму для обчислення рангу вільної підгрупи. Формула для обчислення рангу дається в гіпотезі Бірча і Свіннертона-Дайера.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Крім того,

${\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}}$

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

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

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

$\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.

Література

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