Відкрити головне меню

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

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

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

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

Канонічна формаРедагувати

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

 .

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

 .

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

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

або

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

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

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

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

 ,

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

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

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

 

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

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

Груповий законРедагувати

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

 

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

Ця група може бути описана і алгебрично. Нехай задані крива   над полем   (характеристика якого не рівна ні 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. Якщо  ,   та  , тоді   де
     
     
  4. Якщо  ,   , ,  , тоді   , де
     
     

У даному огляді не приводиться огляд додавання в проективних координатах. Для переходу від афінних до проективних координат і навпаки існують відповідні формули трансформації.

ЗастосуванняРедагувати

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

З 1998 року використовування еліптичних кривих для розв'язування криптографічних завдань, таких як цифровий підпис, було закріплено у стандартах США ANSI X9.62 та FIPS 186–2, а 2001 року аналогічний стандарт ГОСТ Р34.10–2001 було ухвалено в Росії. В Україні ухвалений стандарт цифрового підпису базується на еліптичних кривих ДСТУ 4145-2002[1].

ПриміткиРедагувати

  1. М. В. Захарченко, О. В. Онацький, Л. Г. Йона, Т. М. Шинкарчук (2011). 2.12 Криптосистема на еліптичних кривих. Асиметричні методи шифрування в телекомунікаціях. ОНАЗ ім. О. С. Попова. ISBN 978-966-7598-71-6. 

ЛітератураРедагувати

  • Н. Коблиц Курс теории чисел и криптографии = 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