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

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

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