Str105

6

Krzywe

eliptyczne

W ostatnich latach pewne pojęcie teorii liczb i geometrii algebraicznej - krzywe eliptyczne (dokładniej, teoria krzywych eliptycznych nad ciałami skończonymi) - znalazło zastosowanie w kryptografii. Podstawowym powodem jest to, że krzywe eliptyczne nad ciałami skończonymi dostarczają niewyczerpanego zasobu grup skończonych, które nawet gdy są duże, łatwo poddają się obliczeniom ze względu na swoją bogatą strukturę. Dotychczas (podrozdział 4.3) mieliśmy do czynienia z multyplikatywnymi grupami ciał. Pod wieloma względami krzywe eliptyczne przypominają te grupy; ale ich przewaga polega na tym, że istnieje większa swoboda w wyborze krzywej eliptycznej niż w wyborze ciała skończonego.

Na początku podamy podstawowe definicje i fakty dotyczące krzywych eliptycznych. Ograniczymy się tylko do pojęć niezbędnych do zrozumienia zastosowań w kryptografii (podrozdziały 6.2 i 6.3), kładąc szczególny nacisk na przykłady kosztem dowodów i ogólności. Czytelnik znajdzie systematyczny wykład tych pojęć w książkach podanych w bibliografii na końcu podrozdziału 6.1.

6.1. Podstawowe pojęcia

W tym podrozdziale K będzie ciałem. Będą nas interesować przede wszystkim ciała: R liczb rzeczywistych, Q liczb wymiernych, C liczb zespolonych oraz skończone ciała F_q mające q = p^T elementów.

Definicja. Niech K będzie ciałem charakterystyki ^2, 3 oraz niech x³ + ax + b (gdzie a, beK) będzie wielomianem trzeciego stopnia bez pierwiastków wielokrotnych. Wtedy krzywą eliptyczną nad ciałem K jest zbiór punktów (x, y), gdzie x, yeK, spełniających równanie

y² m x³ f ax + b,    (1)

wraz z elementem oznaczanym przez O i zwanym „punktem w nieskończoności” (o którym powiemy więcej w dalszym ciągu).

Mli K jest ciałem charakterystyki 2, to krzywą eliptyczną nad ciałem K nazywamy zbiór punktów spełniających równanie jednego z następujących dwóch typów:

y¹ + cy - x^s + ax + ó    (2a)

lub

y² 4- jc)' = x³ + ax² + b    (2b)

(nie jest istotne w tym przypadku, czy wielomian po prawej stronie ma pierwiastki wielokrotne) wraz z „punktem w nieskończoności” O.

Jeśli AT jest ciałem charakterystyki 3, to krzywą eliptyczną nad ciałem K nazywamy zbiór punktów spełniających równanie

y¹ = X³ + ax² + bx + c    (3)

(przy czym wielomian po prawej stronie nie ma pierwiastków wielokrotnych) wraz z „punktem w nieskończoności” O.

Uwagi:

1.    Istnieje ogólna postać równania krzywej eliptycznej nad dowolnym ciałem: y² + a_Yxy + a_zy = x² + a₂x² + a_Kx + a₆, które w ciele Kcharakterystyki różnej od 2 może być przekształcone do postaci y² = x³ + ax² + bx + c (lub do postaci y² = x³ + bx + c, gdy char(K) > 3). W przypadku gdy ciało K ma charakterystykę 2, to równanie może być sprowadzone albo do postaci (2a), albo do postaci (2b).

2.    Jeżeli przez F(x_} y) = 0 oznaczymy równanie (1) (odpowiednio (2), (3)),

określające w sposób uwikłany y jako funkcję zmiennej x, tzn. F(x, y) = = y² - x² - ax - ó (lub F(*, >) = y² + cy +    + ax + b, y² + xy +

+ x² + ax + ó, y² - x² - ax² - bx- c), to punkt (x, y) na krzywej jest punktem nieosobliwym (lub gładkim), jeśli co najmniej jedna pochodna cząstkowa dF/dx, dF/dy jest w tym punkcie różna od zera. (Pochodne wielomianów mogą być zdefiniowane w dowolnym ciele za pomocą zwykłych wzorów; por. punkt 5 na początku rozdziału 2). Nietrudno pokazać, że warunek mówiący, iż wielomian po prawej stronie (1) czy (3) nie ma pierwiastków wielokrotnych jest równoważny żądaniu, by każdy punkt krzywej był nieosobliwy.

Krzywe eliptyczne nad ciałem liczb rzeczywistych. Zanim rozpoczniemy omawianie poszczególnych przykładów krzywych eliptycznych nad różnymi ciałami, pokażemy zasadniczą własność punktów krzywej eliptycznej: mianowicie tworzą one grupę abelową. Aby obrazowo wyjaśnić, jak ta grupa wygląda, założymy na chwilę, żc K = R, tzn. że krzywa eliptyczna jest zwykłą krzywą na płaszczyźnie (wraz z „punktem O w nieskończoności”).