Eliptická křivka daná Weierstrassovou rovnicí
Nechť K je těleso charakteristiky různé od 2 a 3, a, b ∈ K,
4a3 + 27b2 = 0. Pak Weierstrassova rovnice
y2
z = x3
+ axz2
+ bz3
spolu s význačným bodem O = [0, 1, 0] zadává v projektivní rovině
P2(K) eliptickou křivku E.
Tento význačný bod O je jediným bodem na nevlastní přímce
z = 0. Platí dokonce, že nevlastní přímka z = 0 má s eliptickou
křivkou E trojnásobný bod dotyku O, neboť dosazením z = 0 do
rovnice křivky dostaneme x3 = 0.
Ostatní body eliptické křivky jsou vlastní a jsou v afinní rovině
A2(K) = K2 určeny rovnicí y2 = x3 + ax + b.
Je-li A = [α, β, 1] ∈ E, pak i B = [α, −β, 1] ∈ E. Přímka AB má
v P2(K) rovnici x = αz a obsahuje ještě třetí bod na E, totiž O.
Eliptická křivka E : y2
z = x3
+ axz2
+ bz3
, O = [0, 1, 0]
Jsou-li A = [α, β, 1] ∈ E, B = [γ, δ, 1] ∈ E, přičemž α = γ, přímka
AB má v P2(K) rovnici y = βz + (x − αz)k, kde k = δ−β
γ−α .
Hledejme průsečíky přímky AB s eliptickou křivkou E.
Dosazením této rovnice za y do rovnice y2z = x3 + axz2 + bz3 a
vydělením z3 dostaneme kubickou rovnici pro x
z s koeficienty z K:
x
z
3
+ ax
z + b − β + (x
z − α)k
2
= 0.
Jde o normovaný kubický polynom v x
z , jehož dva kořeny α a γ už
známe. Proto má ještě třetí kořen σ ∈ K a z Viétových vztahů
zjistíme, že platí α + γ + σ = k2.
Přímka AB a eliptická křivka E mají tedy ještě třetí průsečík
C = [σ, τ, 1], kde σ = k2 − α − γ, τ = β + k(σ − α).
Někdy může bod C splynout s některým z bodů A, B, v tom
případě mluvíme o dvojnásobném průsečíku.
Eliptická křivka E : y2
z = x3
+ axz2
+ bz3
, O = [0, 1, 0]
Podobně se odvodí, že pokud sestrojíme křivce E v jejím bodě A
tečnu, protne tato tečna křivku E ještě v jednom bodě. Máme tedy
operaci: pro libovolnou dvojici bodů A, B ∈ E je jejím výsledkem
třetí průsečík, který nazveme A B. Tato operace však není
„pěkná : nemá neutrální prvek, není asociativní.
Proto operaci ještě trochu pozměníme pomocí pevně zvoleného
bodu O. Definujeme součet bodů A, B ∈ E předpisem
A + B = (A B) O.
Tato operace sčítání bodů je zřejmě komutativní, (E, +) má
neutrální prvek O a libovolný bod A = [α, β, 1] ∈ E má opačná
bod −A = [α, −β, 1] ∈ E. Je možné dokázat, že operace sčítání
bodů je také asociativní, je tedy (E, +) komutativní grupa.
Důkaz asociativity je mimo možnosti této přednášky.
Explicitní popis operace sčítání bodů
Věta. Nechť K je těleso charakteristiky různé od 2 a 3, a, b ∈ K,
4a3 + 27b2 = 0. Nechť E je eliptická křivka daná Weierstrassovou
rovnicí y2z = x3 + axz2 + bz3 s význačným bodem O = [0, 1, 0].
Operaci + na E je možné popsat takto:
1. Pro libovolné A ∈ E klademe A + O = O + A = A.
2. Pro libovolné A = [α, β, 1] ∈ E je také B = [α, −β, 1] ∈ E a
klademe A + B = O. (Tento bod B pak označujeme −A.)
3. Pro libovolné A = [α, β, 1] ∈ E, B = [γ, δ, 1] ∈ E takové, že
B = −A, položme
k =
β−δ
α−γ je-li A = B,
3α2+a
2β je-li A = B,
σ = k2
− α − γ,
τ = −β + k(α − σ),
pak platí [σ, τ, 1] ∈ E a klademe A + B = [σ, τ, 1] ∈ E.
Věty o eliptických křivkách nad konečnými tělesy
Projektivní rovina nad konečným tělesem má konečně mnoho bodů,
proto eliptická křivka nad konečným tělesem je konečná grupa.
Věta. (Hasse)
1. Nechť p je prvočíslo a (E, O) je eliptická křivka nad Fp. Pak
|E| = p + 1 − ap, kde celé číslo ap splňuje |ap| < 2
√
p.
2. Označme αp ∈ C kořen rovnice x2 − apx + p = 0. Pro
libovolné n ∈ N nechť (En, O) je eliptická křivka nad Fpn
určená stejnou Weierstrassovou rovnicí jako (E, O) (to má
smysl, neboť Fp ⊆ Fpn ). Pak platí |En| = pn + 1 − 2 Re(αn
p),
kde Re značí reálnou část komplexního čísla.
Věta. Nechť (E, O) je eliptická křivka nad konečným tělesem Fq,
kde q je mocnina prvočísla. Pak (E, +) je cyklická grupa nebo
součin dvou cyklických grup. Navíc, ve druhém případě, je-li (E, +)
izomorfní se součinem cyklických grup o d1 a d2 prvcích, přičemž
d1 | d2, pak platí d1 | q − 1.
Věty o eliptických křivkách nad Q
Věta. (Mordell) Nechť (E, O) je eliptická křivka nad Q. Pak (E, O)
je konečně generovaná grupa. Jinými slovy: označme (E , +)
podgrupu prvků konečného řádu v grupě (E, +) (tzv. torzní
podgrupa); pak existuje (jednoznačně určené) nezáporné celé číslo
r tak, že (E, +) je izomorfní se součinem (E , +) × (Z, +)r .
Věta. (Mazur) Nechť (E, O) je eliptická křivka nad Q. Pak její
torzní podgrupa je izomorfní s některou z následujících 15 grup:
(Z/mZ, +) pro 1 ≤ m ≤ 10 nebo m = 12
(Z/2Z, +) × (Z/2mZ, +) pro 1 ≤ m ≤ 4
(a každá z uvedených grup je torzní grupa některé eliptické křivky
nad Q).
Proč si povídáme o eliptických křivkách?
Eliptické křivky se využívají v některých testech na prvočíselnost i
v algoritmech hledání netriviálního dělitele.
Za tím účelem je třeba pracovat také s „eliptickými křivkami nad
okruhem ZN zbytkových tříd modulo N i v případě, že přirozené
číslo N není prvočíslo. Ovšem projektivní prostor je definován jen
nad tělesem, což v tomto případě ZN není (proto ty uvozovky).
Proto budeme definovat pojem projektivního prostoru i nad
okruhem ZN pro libovolné přirozené číslo N.
Projektivní prostor nad okruhem ZN
Definice. Nechť N je přirozené číslo (ne nutně prvočíslo). Pak
n-rozměrným projektivním prostorem nad okruhem ZN rozumíme
rozklad na následující množině (n+1)-tic zbytkových tříd modulo N
M = {([u1]N, . . . , [un+1]N); u1, . . . , un+1 ∈ Z, (N, u1, . . . , un+1) = 1}
příslušný ekvivalenci ∼, kterou definujeme takto: pro libovolné
(n + 1)-tice ([u1]N, . . . , [un+1]N), ([v1]N, . . . , [vn+1]N) ∈ M
položíme ([u1]N, . . . , [un+1]N) ∼ ([v1]N, . . . , [vn+1]N) právě tehdy,
když existuje λ ∈ Z, (λ, N) = 1, které pro každé i ∈ {1, . . . , n + 1}
splňuje podmínku [ui ]N = [λvi ]N.
V tomto n-rozměrném projektivním prostoru Pn(ZN) nad ZN
budeme třídu rozkladu (tj. bod projektivního prostoru) obsahující
(n + 1)-tici ([u1]N, . . . , [un+1]N) značit [[u1]N, . . . , [un+1]N].
Poznámka. Pro libovolné d | N homomorfismus okruhů ZN → Zd
určený předpisem [u]N → [u]d pro každé a ∈ Z indukuje zobrazení
n-rozměrných projektivních prostorů Pn(ZN) → Pn(Zd ).
„Eliptická křivka nad okruhem ZN
Definice. Mějme dána celá čísla a, b a zvolme přirozené číslo N
tak, že (4a3 + 27b2, N) = 1. Pak
EN = [x]N, [y]N, [z]N ∈ P2
(ZN); y2
z ≡ x3
+axz2
+bz3
(mod N)
spolu s význačným bodem O = [0]N, [1]N, [0]N je „eliptická
křivka nad okruhem ZN.
Poznámka. Jestliže [x1]N, [y1]N, [z1]N = [x2]N, [y2]N, [z2]N , pak
y2
1 z1 ≡ x3
1 +ax1z2
1 +bz3
1 (mod N) ⇔ y2
2 z2 ≡ x3
2 +ax2z2
2 +bz3
2 (mod N).
Definice je tedy korektní.
Věta. Jestliže d | N, pak zobrazení f : P2(ZN) → P2(Zd ), určené
předpisem f [x]N, [y]N, [z]N = [x]d , [y]d , [z]d , lze zúžit na
zobrazení f : EN → Ed .
Částečná operace na „eliptické křivce nad okruhem ZN
Pro a, b ∈ Z a N ∈ N splňující (4a3 + 27b2, N) = 1 definujme na
„eliptické křivce EN částečnou operaci + pomocí vzorců
odvozených pro eliptické křivky nad tělesy, pokud se tyto vzorce
dají použít. Jediné místo, kdy mohou nastat potíže, je v situaci,
kdy chceme dělit, abychom našli směrnici k tečny nebo přímky
spojující dva body „eliptické křivky . Konkrétněji je to tehdy, když
chceme dělit zbytkovou třídou [u]N = [0]N takovou, že [u]N /∈ Z×
N.
V tom případě je (u, N) netriviální dělitel čísla N.
Avšak naším cílem bude rozhodnout o prvočíselnosti čísla N,
popřípadě najít jeho netriviálního dělitele. Pokud se tedy
dostaneme do situace, že neumíme na EN sečíst dva body, budeme
hotovi. Proto nám nevadí, že operace + je jen částečná.
Pro libovolné d | N je dříve zmíněné zobrazení f : EN → Ed , určené
předpisem f [x]N, [y]N, [z]N = [x]d , [y]d , [z]d , částečný
homomorfismus: pro libovolné A, B ∈ EN takové, že máme
definován součet A + B, platí f (A + B) = f (A) + f (B).