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

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

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

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

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

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

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

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

Графіки кривих 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}$-^[en]${\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_{R}-x_{P})~}$.

Звідси

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

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

Якщо ${\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 x_{2P}=s^{2}-2x_{P}~}$,

${\displaystyle y_{2P}=s(x_{P}-x_{2P})-y_{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}}$.

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

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

^[en] стверджує, що якщо поле ${\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})}$ — скінченна абелева група. Вона завжди циклічна або ізоморфна прямій сумі двох циклічних груп. Наприклад, крива, визначена рівнянням ${\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}}}$. Цей результат є окремим випадком гіпотез Вейля. Наприклад, дзета-функція для ${\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.

Див. також

• Рівняння Якобі — Маддена

Примітки

1. Adler M., van Moerbeke P., Vanhaecke P. (2004). [Integrable Spinning Tops. In: Algebraic Integrability, Painlevé Geometry and Lie Algebras Integrable Spinning Tops. In: Algebraic Integrability, Painlevé Geometry and Lie Algebras]. Springer, Berlin, Heidelberg. ISBN .
2. Washington, Lawrence C. Elliptic curves: number theory and cryptography. CRC press, 2008. - c. 97
3. Koblitz 1994, p. 158
4. Koblitz 1994, p. 160
5. М. В. Захарченко, О. В. Онацький, Л. Г. Йона, Т. М. Шинкарчук (2011). 2.12 Криптосистема на еліптичних кривих. Асиметричні методи шифрування в телекомунікаціях. ОНАЗ ім. О. С. Попова. ISBN .

Література

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