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 (αn
p),
kde 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 = Z/NZ 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 = {([a1]N, . . . , [an+1]N); a1, . . . , an+1 ∈ Z, (N, a1, . . . , an+1) = 1}
příslušný ekvivalenci ∼, kterou definujeme takto: pro libovolné
(n + 1)-tice ([a1]N, . . . , [an+1]N), ([b1]N, . . . , [bn+1]N) ∈ M
položíme ([a1]N, . . . , [an+1]N) ∼ ([b1]N, . . . , [bn+1]N) právě tehdy,
když existuje λ ∈ Z, (λ, N) = 1, které pro každé i ∈ {1, . . . , n + 1}
splňuje podmínku [ai ]N = [λbi ]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 ([a1]N, . . . , [an+1]N) značit [[a1]N, . . . , [an+1]N].
Poznámka. Pro libovolné d | N homomorfismus okruhů ZN → Zd
určený předpisem [a]N → [a]d pro každé a ∈ Z indukuje zobrazení
n-rozměrných projektivních prostorů Pn(ZN) → Pn(Zd ).
Test na prvočíselnost
Dáno přirozené číslo N > 1, o kterém jsme testem Millera a
Rabina zjistili, že N je asi prvočíslo. Můžeme také předpokládat, že
víme, že N není dělitelné malými prvočísly. Test na prvočíselnost
má dokázat, že N skutečně prvočíslem je, anebo to vyvrátit.
Známe už N − 1 test Pocklingtona a Lehmera. Ten pracuje dobře,
pokud jsme schopni dostatečně rozložit číslo N − 1. Pokud však
neexistuje dost velký dělitel F|N − 1, který jsme schopni rozložit na
prvočinitele, tato metoda neuspěje. Pak můžeme ještě zkusit N + 1
test, ten však vyžaduje rozložit dost velkého dělitele čísla N + 1,
což se však často také nemusí podařit a skončíme nezdarem.
Řešení nabízí teorie eliptických křivek: je-li N skutečně prvočíslo,
máme spoustu eliptických křivek nad ZN. Jejich řády jsou rovny
přirozeným číslům v intervalu (N + 1 − 2
√
N, N + 1 + 2
√
N). Je
pravděpodobné, že nezanedbatelnou část z těchto čísel budeme
schopni rozložit na prvočinitele.
Síla metody eliptických křivek je v jejich počtu: pokud nevyhovuje
několik konkrétních křivek, nevadí, vezmeme další.
Opakování N − 1 testu Pocklingtona a Lehmera
Předpokládáme, že známe prvočíslo p dělící N − 1, přitom pαp je
nejvyšší mocnina p dělící N − 1.
Dále označme d libovolné neznámé prvočíslo dělící N.
Máme homomorfismus okruhů f : ZN → Zd , kde f ([a]N) = [a]d
pro každé a ∈ Z. Homomorfismus f je dobře definován, neboť
d | N. Protože je d prvočíslo, je druhý okruh těleso Fd = Zd .
Předpokládáme existenci ap ∈ Z, které splňuje
aN−1
p ≡ 1 (mod N) a (a
N−1
p
p − 1, N) = 1.
Označme b = f ([ap]N) ∈ Fd . Pak bN−1 = 1, b
N−1
p = 1, a tedy řád
prvku b je dělitelný pαp , odkud pαp | |F×
d | = d − 1, tedy
d ≡ 1 (mod pαp ). Získali jsme tím informaci o neznámém d.
Klíčem k úspěchu zde byl homomorfismus f : ZN → Zd .
Přestože jsme neznali d, a tedy nebyli schopni v Zd pracovat,
počítali jsme ve známém okruhu ZN a výsledky výpočtů jsme do
Zd zobrazili homomorfismem f .
Test na prvočíselnost pomocí eliptických křivek
Přejděme k eliptickým křivkám, opět d značí libovolné neznámé
prvočíslo dělící dané N, (N, 6) = 1. Zvolme libovolně a, b ∈ Z
taková, že (4a3 + 27b2, N) = 1. Rovnice y2z = x3 + axz2 + bz3
nám dává „eliptickou křivku EN, na níž máme definovánu
částečnou operaci, a eliptickou křivku Ed , což je komutativní
grupa. Z Hasseho věty víme, že ||Ed | − d − 1| < 2
√
d.
Přestože v Ed nejsme schopni počítat (vždyť neznáme d), máme
částečný homomorfismus f : EN → Ed , kterým můžeme výpočet
provedený v EN zobrazit do Ed . Víme, že f ([[0]N, [1]N, [0]N]]) = O
a že pro libovolný P = [[u]N, [v]N, [1]N]] ∈ EN platí f (P) = O.
Je-li q prvočíslo a bod P = [[u]N, [v]N, [1]N]] ∈ EN takový, že
máme definované q · P = P + P + · · · + P = [[0]N, [1]N, [0]N]], pak
řád bodu f (P) v grupě Ed je q, a tedy (
√
d + 1)2 > |Ed | ≥ q.
Najdeme-li takový bod P pro prvočíslo q > ( 4
√
N + 1)2, plyne
odtud d >
√
N, a tedy N je prvočíslo.
Problém je, jak volit čísla a, b a jak najít prvočíslo q a bod P ∈ EN
s potřebnými vlastnostmi. . .
Goldwasser - Kilian, 1986
Řešení navržené Goldwasserem a Kilianem má spíše teoretický
význam; je možné dokázat, že platí-li jistá hypotéza o rozložení
prvočísel v krátkých intervalech, pak očekávaný čas výpočtu je
O(ln12
N), tedy polynomiální.
Existuje algoritmus Schoofa, který pro prvočíslo p počítá řád (tj.
počet bodů) dané eliptické křivky nad Fp v čase O(ln8
p).
Zvolíme náhodně a, b ∈ Z tak, aby (4a3 + 27b2, N) = 1. Pomocí
Schoofova algoritmu určíme pro křivku (E, O) určenou rovnicí
y2 = x3 + ax + b a pro p = N její řád m (jestliže N není prvočíslo,
nemá m žádný význam). Získané m zkoušíme dělit malými
prvočísly s nadějí, že poté, co odstraníme malé faktory, zůstane
nám q > ( 4
√
N + 1)2, q < N
2 , o kterém test Millera a Rabina zjistí,
že q je asi prvočíslo. Pokud se nám to nepodaří, začneme znovu
s jinými a, b ∈ Z.
Existuje algoritmus, který pro prvočíslo p a celé číslo e hledá v čase
O(ln4
p) řešení kongruence x2 ≡ e (mod p) a to, že takové řešení
neexistuje, zjistí dokonce v čase O(ln2
p).
Goldwasser - Kilian, 1986, pokračování
Najdeme bod P na křivce: náhodně zvolíme c ∈ ZN a hledáme
d ∈ ZN tak, aby d2 = c3 + ac + b (jde o kongruenci modulo N;
d hledáme jako by bylo N prvočíslo, pak uděláme zkoušku, pokud
nevyjde, nebylo N prvočíslo a jsme zcela hotovi). Neexistuje-li
takové d, zkusíme jiné c. Pak za P zvolíme m
q -násobek bodu
[c, d, 1] v (E, +). Je-li P = [0, 1, 0], zvolíme jiné c atd. Je-li
P = [0, 1, 0], pak platí P = [x, y, 1] pro nějaké x, y ∈ ZN.
Spočítáme q-násobek bodu P v (E, +). Není-li definován, našli
jsme netriviálního dělitele čísla N. Jestliže nedostaneme [0, 1, 0],
není m řád křivky (E, O), Schoofův algoritmus tedy nedal správný
výsledek a proto N není prvočíslo. Jestliže q-násobek bodu P je
[0, 1, 0], pak je N prvočíslo, pokud q je prvočíslo. To zjistíme
rekurzívně (N0 = N, N1 je q pro N0, N2 je q pro N1, . . . ).
S rekurzí skončíme v okamžiku, kdy Ni je dost malé na to,
abychom ověřili jeho prvočíselnost pokusným dělením (to nastane
v O(ln N) krocích vzhledem k Ni+1 < 1
2Ni ). Je třeba si uvědomit,
že není-li Ni prvočíslo, skončíme jen v případě i = 0, pro i < 0 je
třeba se vrátit k i − 1 a najít nové Ni .