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

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

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

разом з точкою на нескінченності.

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

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

Канонічна форма[ред.ред. код]

Якщо характеристика поля K () не рівна або , то рівняння за допомогою заміни координат приводиться до канонічної форми (форми Вейерштраса):

.

Якщо , то канонічним видом рівняння є:

.

А якщо , то рівняння приводиться до одного з видів:

суперсингулярні криві

або

несуперсингулярні криві.

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

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

Вважаємо, що характеристика поля — не 2 і 3. Тоді еліптична крива — плоска крива, визначена рівнянням вигляду

,

де a і bдійсні числа. Цей вид рівнянь називається рівняннями Вейерштрасса.

Наприклад, на наступному кресленні показані еліптичні криві, визначені рівняннями і . ECClines-3.svg

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

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

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

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

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

ECClines.svg

Тоді ми можемо ввести групову операцію «+» на прямій з такими властивостями: вважатимемо, що невласна точка є нулем групи; і якщо пряма перетинає дану криву в точках , і , то необхідно, щоб у групі. Можна показати, що таким чином крива перетворюється в абелеву групу, тобто в абелевий многовид. Можна також показати, що множина -раціональних точок (включаючи невласну) утворює підгрупу цієї групи. Якщо криву позначити , то така підгрупа звичайно позначається як .

Ця група може бути описана і алгебрично. Нехай задані крива над полем (характеристика якого не рівна ні 2, ні 3), і точки і на кривій, допустимо, що . Хай ; оскільки - поле, то чітко визначено. Тоді ми можемо визначити таким чином:

,
.

Якщо , то у нас два варіанти: якщо , то сума визначена як 0; значить, обернену точку до будь-якої точки на кривій можна знайти, через її симетричне відображення по осі . Якщо , то визначається так:

,
,
.

Якщо , то .

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

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

.

Тут і — константи; — еліптична функція Вейєрштрасса, а — її похідна. Видно, що співвідношення—у вигляді еліптичної кривої (над комплексними числами). Функції Вейерштрасса двічі періодичні; тобто, вони є періодичними у відношенні ґратки По суті, функції Вейєрштрасса натурально визначені на торі . Цей тор може бути вкладений в комплексну проектну площину відображенням

.

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

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

.

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

і

,

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

.

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

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

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

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

,

де і — такі елементи , що многочлен (права сторона) не має кратного кореня. (Якщо характеристика рівна 2 або 3, то необхідно ввести ще декілька умов.)

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

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

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

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

Точне число раціональних точок еліптичної кривої над скінченним полем достатньо важко обчислити, але теорема Хассе стверджує, що

.

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

Застосування[ред.ред. код]

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

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

Еліптична крива над скінченним полем є множина пар (x,y) елементів цього поля, що задовольняють афінне рівняння еліптичної кривої в нормальній формі Веєрштраса

де , , разом із приєднаною нескінченною віддаленою точкою О. Пара (x,y) елементів основного поля називається афінними координатами точки еліптичної кривої. Нескінченно віддалена точка О не має афінних координат. Елементи А, В основного поля називаються коефіцієнтами рівняння еліптичної кривої. Число точок еліптичної кривої разом з нескінченною точкою називається порядком еліптичної кривої.

Поряд з афінними координатами точки також існують проективні координати. Класичне рівняння Веєрштраса для таких координат має вигляд:

а точками проективної еліптичної кривої є трійки елементів основного поля (x:y:z).

При додаванні точок еліптичної кривої, як результат ми отримуємо іншу точку цієї кривої. Правила додавання точок еліптичної кривої в афінних координатах можна записати таким чином:
1. для всіх
2. Якщо , тоді . Точка (x,x+y) позначається як –P і називається мінус P, точка –P також є точкою даної еліптичної кривої.
3. Якщо

де
тоді де




Геометричну ілюстрацію додавання можна побачити на рис. 1.1


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


4. Якщо , ,, , тоді , де

Геометричну ілюстрацію подвоєння можна побачити на рис. 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