Перегляд вихідного коду сторінки Еліптична крива

[[Image:EllipticCurveCatalog.svg|right|thumb|392px|Приклади еліптичних кривих над дійсними числами, визначених рівняннями вигляду y<sup>2</sup>&nbsp;=&nbsp;x<sup>3</sup>&nbsp;+&nbsp;a&nbsp;x&nbsp;+&nbsp;b, на області [-3,3]<sup>2</sup>. Крива при a&nbsp;=&nbsp;b&nbsp;=&nbsp;0 не еліптична.]]

'''Еліптична крива''' над [[поле (алгебра)|полем]] ''K''&nbsp;— це [[множина]] точок [[Проєктивна площина|проективної площини]] над ''K'', що задовольняють рівнянню

: <math>y^2+a_1 xy+a_3 y=x^3+a_2 x^2+a_4 x+a_6 ~</math>

разом з [[Точка на нескінченності|точкою на нескінченності]] та не містить [[особлива точка|особливих точок]].
 
Еліптичні криві є одним з основних об'єктів вивчення в сучасній [[теорія чисел|теорії чисел]] і [[криптографія|криптографії]]. Наприклад, вони були використані при доведенні [[Велика теорема Ферма|Великої теореми Ферма]]. [[Еліптична криптографія]] є самостійним розділом криптографії, що присвячений вивченню криптосистем на базі еліптичних кривих. Еліптичні криві також застосовуються в деяких алгоритмах [[факторизація|факторизації]] (наприклад {{не перекладено|Алгоритм Ленстри (розкладання на множники)|Алгоритм Ленстри|en|Lenstra elliptic-curve factorization}}) і [[тест простоти|тестування простоти]] чисел. Зокрема, у [[Класична механіка|класичній механіці]] за допомогою їх можна описати рух [[Дзиґа|дзиґи]].<ref>{{cite book
 | author = Adler M., van Moerbeke P., Vanhaecke P. | year = 2004
 | title = Integrable Spinning Tops. In: Algebraic Integrability, Painlevé Geometry and Lie Algebras
 | url = Integrable Spinning Tops. In: Algebraic Integrability, Painlevé Geometry and Lie Algebras | url-access = registration 
 | publisher = Springer, Berlin, Heidelberg
 | isbn=978-3-642-06128-8
 }}</ref>

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

== Еліптичні криві над дійсними числами ==
[[Файл:ECClines-3.svg|frame|right|Графіки кривих {{nobr|1=''y''<sup>2</sup> = ''x''<sup>3</sup> − ''x''}} та {{nobr|1=''y''<sup>2</sup> = ''x''<sup>3</sup> − ''x'' + 1}}]]

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

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

: <math>y^2 = x^3 + ax + b~</math>,

де <math>a</math> і <math>b</math>&nbsp;— [[дійсні числа]].

Визначення еліптичної кривої також вимагає, щоб така крива не мала особливих точок. Геометрично це значить, що графік не повинен мати [[Касп (математика)|каспів]] та самоперетинів. Алгебрично це виконується [[Тоді й лише тоді|тоді і тільки тоді]], коли [[дискримінант]]

: <math>\Delta = -16(4a^3 + 27b^2)~</math>

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

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

== Груповий закон ==
[[Файл:Graph1.png‎|thumb|Геометрична ілюстрація додавання точок на еліптичній кривій]]
[[Файл:Graph2.png‎|thumb|Геометрична ілюстрація подвоєння]]

При роботі в [[Проєктивний простір|проективному просторі]] можна побудувати групову структуру на будь-якій кубічній кривій. Крива, яка задовольняє рівняння у вигляді Вейєрштрасса, матиме точку на нескінченності <math>O</math> з [[Однорідні координати|однорідними координатами]] <math>(0:1:0)</math>, яка буде [[Нейтральний елемент|нейтральним елементом]] в групі.

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

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

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

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

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

Вищеописану групу можна визначити як алгебраїчно, так і геометрично. Нехай крива задовольняє рівняння <math>y^2 = x^3 + ax + b</math> над полем <math>K</math> (характеристика якого не рівна 2, 3), точки <math>P = (x_P, y_P)</math> та <math>Q = (x_Q, y_Q)</math> лежать на цій кривій. Спочатку розглянемо випадок, коли <math>x_P \ne x_Q</math> (перший рисунок нижче). Нехай <math>y = sx + d</math>&nbsp;— пряма, що проходить через P і Q, тоді вона матиме такий кутовий коефіцієнт:

: <math>s=\frac{y_P-y_Q}{x_P-x_Q}~</math>

Оскільки <math>K</math>&nbsp;— поле, то <math>s</math> визначений. Рівняння прямої та рівняння кривої мають однакові значення <math>y</math> у точках <math>x_P</math>, <math>x_Q</math> та <math>x_R</math>.

: <math>(sx+d)^2=x^3+ax+b~</math>

яке еквівалентне <math>0 = x^3 - s^2x^2 - 2sdx + ax + b - d^2</math>. Ми знаємо, що це рівняння має корені <math>x_P</math>, <math>x_Q</math> та <math>x_R</math>. Запишемо

: <math>(x-x_P)(x-x_Q)(x-x_R)=x^3-(x_P+x_Q+x_R)x^2+(x_Px_Q+x_Px_R+x_Qx_R)x-x_Px_Qx_R~</math>

З прирівняння коефіцієнтів при <math>x^2</math> та з рівняння прямої через дві точки знаходимо значення <math>x_R</math> та <math>y_R</math>. Таким чином отримаємо <math>R = (x_R, y_R) = -(P + Q)</math>, де

: <math>x_R = s^2 - x_P - x_Q~</math>,
: <math>y_R = y_P + s(x_R - x_P)~</math>.

Звідси

: <math>x_{P + Q} = s^2 - x_P - x_Q~</math>,
: <math>y_{P + Q} = s(x_P - x_{P + Q}) - y_P~</math>.

Якщо <math>x_P = x_Q</math>, то існує два варіанти:

: 1) <math>y_P = -y_Q</math> (третій та четвертий рисунки нижче), включаючи випадок, коли <math>y_P = y_Q = 0</math> (четвертий рисунок), тоді сума точок <math>P</math> та <math>Q</math> дорівнюватиме <math>O</math>. Таким чином протилежною до кожної точки є точка симетрична відносно осі <math>Ox</math>. 
: 2) <math>y_P = y_Q \ne 0</math>, тоді <math>Q = P</math> та <math>R = (x_R, y_R) = - (P + P) = -2P = -2Q</math> (другий рисунок) знаходиться наступним чином:

: <math>s = \frac{3x_P^2 + a}{2y_P}~</math>,
: <math>x_R = s^2 - 2x_P~</math>,
: <math>y_R = y_P + s(x_R - x_P)~</math>.

Звідси

: <math>x_{2P} = s^2 - 2x_P~</math>,
: <math>y_{2P} = s(x_P - x_{2P}) - y_P~</math>.

<div class="center">
[[Файл:ECClines.svg]]
</div>

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

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

: <math>\wp'(z)^2 = 4\wp(z)^3 -g_2\wp(z) - g_3</math>.

Тут <math>g_2</math> і <math>g_3</math>&nbsp;— константи; <math>\wp(z)</math>&nbsp;— еліптична функція Вейєрштрасса, а <math>\wp'(z)</math>&nbsp;— її [[похідна]]. Видно, що співвідношення—у вигляді еліптичної кривої (над комплексними числами). Функції Вейерштрасса двічі періодичні; тобто, вони є періодичними у відношенні ґратки <math>\Lambda.</math> По суті, функції Вейєрштрасса натурально визначені на торі <math>T=\mathbb{C}/\Lambda</math>. Цей тор може бути вкладений в комплексну проектну площину відображенням

: <math>z\to (1,\wp(z) \wp'(z))</math>.

Це відображення&nbsp;— груповий [[ізоморфізм]], що відображає структуру натуральної групи тора в проективну площину. Крім того, це ізоморфізм [[поверхня Рімана|поверхонь Рімана]], тобто, топологічно, дану еліптичну криву можна розглянути як тор. Якщо ґратка <math>\Lambda</math> пов'язана із ґраткою <math>c\Lambda</math> множенням на ненульове комплексне число <math>c</math>, то відповідні криві ізоморфні. Класи ізоморфізму еліптичних кривих визначені [[j-інваріант]]ом.

Класи ізоморфізму можна розглянути простішим способом. Константи <math>g_2</math> і <math>g_3</math>, що називаються [[модулярний інваріант|модулярними інваріантами]], єдиним чином визначені структурою тора. Втім, комплексні числа є [[поле розкладу|полем розкладу]] для многочленів, а значить, еліптичні криві можна записати як

: <math>y^2=x(x-1)(x-\lambda)</math>.

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

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

і

: <math>g_3=\frac{1}{27} (\lambda+1)(2\lambda^2-5\lambda+2)</math>,

отже [[Еліптичні функції Веєрштрасса#Модулярний дискримінант|модулярний дискримінант]] рівний

: <math>\Delta = g_2^3-27g_3^2 = \lambda^2(\lambda-1)^2</math>.

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

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

{{не перекладено|Теорема Морделла — Вейля||en|Mordell–Weil theorem}} стверджує, що якщо поле <math>K</math>&nbsp;— поле [[раціональне число|раціональних чисел]] (або, взагалі [[Алгебраїчне числове поле|числовим полем]]), то група <math>K</math>-[[Раціональна точка|раціональних точок]] є скінченно породженою. Це означає, що група може бути виражена як пряма сума [[вільна абелева група|вільної абелевої групи]] і скінченної [[підгрупа кручення|підгрупи кручення]]. Хоч і відносно легко визначити підгрупу кручення <math>E(K)</math>, але немає загального алгоритму для обчислення [[ранг абелевої групи|рангу]] вільної підгрупи. Формула для обчислення рангу дається в [[Гіпотеза Берча і Свіннертона-Даєра|гіпотезі Бірча і Свіннертона-Даєра]].

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

Точне число раціональних точок еліптичної кривої <math>E</math> над [[скінченне поле|скінченним полем]] <math>\mathbb{F}_p</math> достатньо важко обчислити, але [[Теорема Гассе про еліптичні криві|теорема Гассе]] стверджує, що

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

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

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

Еліптичні криві можуть бути визначені над довільним [[Поле (алгебра)|полем]] <math>K</math>; формально, еліптична крива визначається як невироджена проектна алгебрична крива над <math>K</math> з [[рід (математика)|родом]] 1 з заданою точкою, визначеною над <math>K</math>.

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

: <math>y^2=x^3-px-q</math>,

де <math>p</math> і <math>q</math>&nbsp;— такі елементи <math>K</math>, що многочлен <math>x^3-px-q</math> (права сторона) не має кратного кореня. Якщо характеристика рівна 2 або 3, то необхідно ввести ще декілька умов: якщо характеристика поля дорівнює ''3'', то загальне рівняння можна звести до вигляду

: <math>y^2 = 4x^3+b_2x^2+b_4x+b_6~</math>,

де <math>b_2</math>, <math>b_4</math>, <math>b_6</math>&nbsp;— константи, і поліном праворуч має тільки прості корені (позначення обрано з історичних причин). У полі характеристики 2 багато чого неможливо, тому загальне рівняння залишається без змін

: <math>y^2+a_1 xy+a_3 y=x^3+a_2 x^2+a_4 x+a_6~</math>

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

Можна узяти криву як множину всіх точок <math>(x,y)</math>, які задовольняють вищезгаданому рівнянню, а <math>x</math> і <math>y</math> одночасно є елементами [[Алгебричне розширення|алгебричного замикання]] поля <math>K</math>. Точки кривої, обидві координати яких належать <math>K</math>, називаються '''<math>K</math>-[[Раціональна точка|раціональними точками]]'''.

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

[[File:Elliptic curve on Z61.svg|thumb|right|275px|Множина скінченних точок еліптичної кривої ''y''<sup>2</sup> = ''x''<sup>3</sup> − ''x'' над скінченним полем '''F'''<sub>61</sub>.]]

Нехай <math>K=\mathbb{F}_q</math> [[Поле Галуа|скінченне поле]] з <math>q</math> елементів та <math>E</math> еліптична крива визначена над <math>K</math>. Точну кількість [[Раціональна точка|раціональних точок]] еліптичної кривої <math>E</math> над <math>K</math> взагалі досить важко обчислити. [[Теорема Гассе про еліптичні криві]] дає, враховуючи точку на нескінченності, таку оцінку:
:<math>|\# E(K) - (q + 1) | \le 2\sqrt{q}</math>

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

[[File:Elliptic curve on Z71.svg|thumb|left|275px|Множина скінченних точок еліптичної кривої ''y''<sup>2</sup> = ''x''<sup>3</sup> − ''x'' над скінченним полем '''F'''<sub>71</sub>.]]

Множина точок <math>E(\mathbb{F}_q)</math>&nbsp;— скінченна [[абелева група]]. Вона завжди циклічна або [[Ізоморфізм груп|ізоморфна]] [[Пряма сума|прямій сумі]] двох циклічних груп. <ref>Washington, Lawrence C. Elliptic curves: number theory and cryptography. CRC press, 2008. - c. 97</ref> Наприклад,<ref>{{Harvard citations|last=Koblitz|year=1994|nb=yes|loc=p. 158}}</ref> крива, визначена рівнянням <math>y^2=x^3-x</math>, над полем <math>\mathbb{F}_{71}</math> має 72 точки (71 скінченних точок враховуючи <math>(0,0)</math> та одна точка на нескінченності) та ізоморфна <math>\mathbb{Z}_{2} \oplus \mathbb{Z}_{36}</math>. Кількість точок на певній кривій можна обчислити через [[Алгоритм Шуфа|алгоритм Шуфа]].

Вивчення кривої над [[Розширення поля|розширеннями поля]] <math>\mathbb{F}_q</math> полегшується введенням [[Локальна дзета-функція|локальної дзета-функції]] для <math>E(\mathbb{F}_q)</math>, визначеної наступним чином
: <math>Z(E(K), T) \equiv \exp \left(\sum_{n=1}^{\infty} \# \left[E(K_n)\right] {T^n\over n} \right)</math>,

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

: <math>Z(E(K), T) = \frac{1 - aT + qT^2}{(1 - T)(1 - qT)}</math>

Крім того,

: <math>\begin{align}
  Z \left(E(K), \frac{1}{qT} \right) &= Z(E(K), T),\\
         1 - aT + qT^2 &= (1 - \alpha T)(1 - \beta T),
\end{align}</math>

де <math>\alpha, \beta \in \mathbb{C}</math> і <math>|\alpha|=|\beta|=\sqrt{q}</math>. Цей результат є окремим випадком [[Гіпотези Вейля|гіпотез Вейля]]. Наприклад,<ref>{{Harvard citations|last=Koblitz|year=1994|nb=yes|loc=p. 160}}</ref> дзета-функція для <math>E: y^2 + y = x^3</math> над полем <math>F_2</math> дорівнює
: <math>\frac{1 + 2T^2}{(1 - T)(1 - 2T)}</math>

це випливає з того, що
: <math> \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}~</math>.

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

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

З 1998 року використовування еліптичних кривих для розв'язування криптографічних завдань, таких як цифровий підпис, було закріплено у стандартах США ANSI X9.62 та FIPS 186–2. В Україні ухвалений стандарт цифрового підпису базується на еліптичних кривих [[ДСТУ 4145-2002]]<ref name="zakh_2.12">{{cite book
 | title = Асиметричні методи шифрування в телекомунікаціях
 | chapter = 2.12 Криптосистема на еліптичних кривих
 | author = М. В. Захарченко, О. В. Онацький, Л. Г. Йона, Т. М. Шинкарчук
 | publisher = ОНАЗ ім. О. С. Попова
 | year = 2011
 | isbn = 978-966-7598-71-6
}}</ref>.

== Див. також ==
* [[Рівняння Якобі — Маддена]]

== Примітки ==
{{reflist}}

== Література ==

* {{cite book
 | author = Н. Коблиц | year = 2001
 | title = Курс теории чисел и криптографии = A Course in Number Theory and Cryptography
 | publisher = Научное издательство «ТВП»
 | isbn=5-85484-014-6
 }}
* {{cite book
 | author = Н. Коблиц | year = 2000
 | title = Введение в эллиптические кривые и модулярные формы = Introduction to Elliptic Curves and Modular Forms
 | publisher = ИО НФМИ
 | isbn=5-8032-3325-0
 }}
* {{cite book
 | author = С. Ленг | year = 2000
 | title = Эллиптические функции = Elliptic functions
 | publisher = ИО НФМИ
 | isbn=5-8032-3326-9
 }}
* {{cite book
 | author = Joseph H. Silverman | year = 1986
 | title = The Arithmetic of Elliptic Curves
 | publisher = Springer
 | isbn=0-387-96203-4
 }}
* {{cite book
 | author = Lawrence Washington | year = 2003
 | title = Elliptic Curves: Number Theory and Cryptography
 | url = https://archive.org/details/ellipticcurvesnu0000wash | url-access = registration | publisher = Chapman & Hall/CRC
 | isbn=1-58488-365-0
 }}
{{Криві}}
{{Крипто навігація}}
{{ВП-портали|Програмування|Інформаційні технології|Математика}}
{{Crypto-stub}}
{{Refimprove|дата=серпень 2017}}
[[Категорія:Еліптичні криві]]
[[Категорія:Теорія груп]]