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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Еліптична крива над полем 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~. ECexamples01.png

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

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

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

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

Груповий закон[ред.ред. код]

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

ECClines.svg

Тоді ми можемо ввести групову операцію «+» на прямій з такими властивостями: вважатимемо, що невласна точка є нулем групи; і якщо пряма перетинає дану криву в точках 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


Graph1.png
Рис 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


Graph2.png
Рис 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