Užití věty Pocklingtona a Lehmera
Věta. Nechť N je přirozené číslo, N > 1. Nechť p je prvočíslo dělící
N − 1. Předpokládejme dále, že existuje ap ∈ Z tak, že
aN−1
p ≡ 1 (mod N) a a
N−1
p
p − 1, N = 1. (1)
Nechť pαp je nejvyšší mocnina p dělící N − 1. Pak pro každý
kladný dělitel d čísla N platí d ≡ 1 (mod pαp ).
Důsledek. Nechť N ∈ N, N > 1. Předpokládejme, že můžeme psát
N − 1 = F · U, kde (F, U) = 1 a F >
√
N, přičemž známe rozklad
čísla F na prvočinitele. Pak platí:
jestliže pro každé prvočíslo p | F můžeme najít ap ∈ Z
splňující (1) z předchozí věty, pak je N prvočíslo;
je-li N prvočíslo, pak pro libovolné prvočíslo p | N − 1 existuje
ap ∈ Z splňující (1), například primitivní kořen modulo N;
nalezneme-li 1 < ap < N tak, že aN−1
p ≡ 1 (mod N), je N
složené.
Zesílení užití věty Pocklingtona a Lehmera
Důsledek. Nechť N ∈ N, N > 1. Předpokládejme, že můžeme psát
N − 1 = F · U, kde (F, U) = 1, přičemž známe rozklad čísla F na
prvočinitele. Dále předpokládejme, že všechna prvočísla dělící U
jsou větší než B ∈ N a že platí B · F ≥
√
N.
Pak platí: jestliže pro každé prvočíslo p | F můžeme najít ap ∈ Z
splňující (1) z předchozí věty a jestliže navíc existuje aU ∈ Z
splňující
aN−1
U ≡ 1 (mod N) a (aF
U − 1, N) = 1,
pak je N prvočíslo.
Je-li naopak N prvočíslo, pak požadovaná ap, aU ∈ Z vždy existují.
Důkaz. Pro každé prvočíslo d | N víme, že d ≡ 1 (mod F). Protože
(aU, N) = 1, existuje e = min{n ∈ N; an
U ≡ 1 (mod d)}. Odtud
e | d − 1, e | N − 1 a e F. Kdyby (e, U) = 1, z e | N − 1 = FU by
plynulo e | F. Je tedy (e, U) > 1 a protože U je dělitelné pouze
prvočísly většími než B, platí (e, U) > B. Protože (F, U) = 1,
z d ≡ 1 (mod e) a d ≡ 1 (mod F) plyne d ≡ 1 (mod F · (e, U)) a
tedy d > F · (e, U) > FB ≥
√
N.
Příklad užití věty Pocklingtona a Lehmera – Pépinův test
Pro k ∈ Z, k > 0, se Fk = 22k
+ 1 nazývá k-té Fermatovo číslo.
Pépinův test: Fk je prvočíslo, právě když 3(Fk −1)/2 ≡ −1 (mod Fk).
Důkaz. „⇐ z důsledku věty Pocklingtona a Lehmera.
„⇒ z kvadratického zákona reciprocity: 3(Fk −1)/2 ≡ 3
Fk
=
= Fk
3 · (−1)
3−1
2
Fk −1
2 = Fk
3 = 2
3 = −1 (mod Fk).
F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537 jsou
prvočísla.
Rozklad čísla Fk na prvočinitele je znám jen pro k ≤ 11.
Fk jsou složená pro každé k = 5, 6, . . . , 32 (ačkoli u F20 ani
F24 není znám žádný prvočíselný dělitel).
Největší Fk, pro které je znám prvočíselný dělitel, je F2543548
dělitelné prvočíslem 9 · 22543551 + 1 (objeveno 22. 6. 2011).
Otevřené problémy: Existuje nekonečně mnoho složených
Fermatových čísel? Existuje nekonečně mnoho Fermatových
čísel, která jsou prvočísla?
Implementace algoritmu (tzv. N − 1 test)
Vstupem je číslo N, které již prošlo testem Millera - Rabina, tedy
číslo, o kterém s vysokou pravděpodobností platí, že je to
prvočíslo. Je třeba to však dokázat.
V první části algoritmu rozkládáme číslo N − 1 na součin F · U a to
tak, že podrobíme N − 1 algoritmu pokusného dělení, ukládáme
získané dělitele a skončíme, až platí BF ≥
√
N, nebo až je B „dost
velké , abychom si byli jisti zastavením v „rozumném čase (zde
B, F, U značí totéž, co v předchozí větě).
Pak náhodně volíme celá čísla ap v intervalu 1 < ap < N a
počítáme bp = a
N−1
p
p mod N a cp = bp
p mod N do té doby, než
cp ≡ 1 (mod N) a (bp − 1, N) = 1.
Je-li N opravdu prvočíslo, podmínku (bp − 1, N) = 1 splňuje
většina z čísel ap, přesněji právě p−1
p (N − 1) čísel z N − 1 čísel
1, 2, . . . , N − 1. Můžeme tedy očekávat, že takové ap brzy
najdeme.
Pokud by však N bylo „velké Carmichaelovo číslo, algoritmus by
se s velkou pravděpodobností nezastavil.
Časová náročnost algoritmu
Není-li N prvočíslo, algoritmus se nemusí zastavit.
Ani pro prvočísla nelze stanovit odhad: záleží na tom, jak snadno
lze rozkládat číslo N − 1. Následné hledání čísel ap je velmi rychlé
(kontrola, zda zvolené ap splňuje podmínku (1) je kvadratické
časové náročnosti, navíc lze volit ap „malá ).
Je možné nerozloženou část U podrobit testu Millera a Rabina a
v případě, že test zjistí, že U je asi prvočíslo, dokázat nejprve
prvočíselnost U (a tedy pracovat rekurzivně).
Zobecnění algoritmu
Je-li N prvočíslo, pak existuje těleso FN2 o N2 prvcích. Jeho
multiplikativní grupa je cyklická řádu N2 − 1 = (N − 1)(N + 1).
Existuje tedy α ∈ FN2 řádu N + 1, tj. splňující αN+1 = 1, avšak
α
N+1
p = 1 pro libovolné prvočíslo p dělící N + 1.
Tuto myšlenku je možno využít pro tzv. N + 1 test analogický
N − 1 testu. V něm vystupuje faktorizace čísla N + 1 místo N − 1.
Pro důkaz prvočíselnosti čísla N lze pak využít informace
o dělitelích čísla N, získané z obou testů.
Podobně lze využít těleso FN3 (a tedy faktorizovat
N3−1
N−1 = N2 + N + 1), těleso FN4 (a faktorizovat N4−1
N2−1
= N2 + 1)
nebo těleso FN6 (a faktorizovat N6−1
(N3−1)(N+1)
= N2 − N + 1).
Vždy nám však už vycházejí čísla podstatně větší než N a tedy
pravděpodobně obtížně rozložitelná.
Některé nezbytnosti z algebraické geometrie
Nechť K je těleso.
Definice. n-rozměrným afinním prostorem nad K rozumíme
kartézskou mocninu Kn. Budeme jej značit An(K), tj.
An
(K) = {(x1, . . . , xn); x1, . . . , xn ∈ K}.
Definice. n-rozměrným projektivním prostorem nad K rozumíme
rozklad na množině Kn+1 − {(0, . . . , 0)} příslušný ekvivalenci ∼,
kterou definujeme takto: pro libovolné (n + 1)-tice (x1, . . . , xn+1),
(y1, . . . , yn+1) ∈ Kn+1 položíme (x1, . . . , xn+1) ∼ (y1, . . . , yn+1)
právě tehdy, když existuje λ ∈ K×, které pro každé
i ∈ {1, . . . , n + 1} splňuje podmínku xi = λyi . Tento n-rozměrný
projektivní prostor nad K budeme značit Pn(K), třídu rozkladu (tj.
bod projektivního prostoru) obsahující (n + 1)-tici (x1, . . . , xn+1)
budeme značit [x1, . . . , xn+1].
Afinní část projektivního prostoru
Nechť x1, . . . , xn+1 jsou z tělesa K, přičemž alespoň jedno z nich je
různé od nuly.
Jestliže xn+1 = 0, pak platí [x1, . . . , xn+1] = [ x1
xn+1
, . . . , xn
xn+1
, 1],
čímž je pevně dán bod ( x1
xn+1
, . . . , xn
xn+1
) ∈ An(K).
Jestliže naopak xn+1 = 0, určuje [x1, . . . , xn+1] jednoznačně bod
[x1, . . . , xn] ∈ Pn−1(K).
Lze tedy n-rozměrný projektivní prostor „rozdělit na n-rozměrný
afinní prostor, který považujeme za množinu „vlastních bodů a na
množinu „nevlastních bodů , která tvoří (n − 1)-rozměrný
projektivní prostor.
Můžeme si představovat, že nevlastní body „leží v nekonečnu.
Toto rozdělení však není kanonické – lze to provést mnoha
způsoby. Tedy to, zda je bod vlastní nebo ne, je věc naší volby.
Nadplochy projektivního prostoru
Máme-li homogenní polynom F(t1, . . . , tn+1) ∈ K[t1, . . . , tn+1]
o n + 1 proměnných nad K stupně k a bod [x1, . . . , xn+1] ∈ Pn(K),
má smysl se ptát, zda F(x1, . . . , xn+1) = 0. Je-li totiž
[x1, . . . , xn+1] = [y1, . . . , yn+1], pak existuje λ ∈ K×, které pro
každé i ∈ {1, . . . , n + 1} splňuje podmínku xi = λyi . Pak ovšem
F(x1, . . . , xn+1) = F(λy1, . . . , λyn+1) = λk · F(y1, . . . , yn+1), a
tedy F(x1, . . . , xn+1) = 0, právě když F(y1, . . . , yn+1) = 0.
Definice. Nechť F(t1, . . . , tn+1) ∈ K[t1, . . . , tn+1] je homogenní
polynom stupně k. Množina
C = {[x1, . . . , xn+1] ∈ Pn
(K); F(x1, . . . , xn+1) = 0}
se nazývá nadplocha stupně k v Pn(K). Je-li n = 2, hovoříme také
o křivce stupně k v projektivní rovině P2(K).
Singulární bod nadplochy projektivního prostoru
Parciální derivací homogenního mnohočlenu je opět homogenní
mnohočlen. Má proto smysl následující definice.
Definice. Nechť F(t1, . . . , tn+1) ∈ K[t1, . . . , tn+1] je homogenní
polynom stupně k a
C = {[x1, . . . , xn+1] ∈ Pn
(K); F(x1, . . . , xn+1) = 0}
příslušná nadplocha. Bod [x1, . . . , xn+1] ∈ C se nazývá singulární,
jestliže pro každé i ∈ {1, . . . , n + 1} platí
∂F
∂xi
(x1, . . . , xn+1) = 0.
Nadplocha C se nazývá singulární, existuje-li alespoň jeden její
singulární bod.
Příklad
Uvažme reálnou projektivní rovinu P2(R).
Abychom se vyhnuli indexům, budeme psát x, y, z místo t1, t2, t3.
Kubický mnohočlen F1(x, y, z) = x3 + x2z − y2z nám definuje
kubickou křivku C1 (tj. křivku stupně 3)
C1 = {[x, y, z] ∈ P2
(R); F1(x, y, z) = 0}.
Jistě [0, 0, 1] ∈ C1. Tento bod je singulární, neboť
∂F1
∂x
= 3x2
+ 2xz,
∂F1
∂y
= −2yz,
∂F1
∂z
= x2
− y2
.
Je tedy C1 singulární křivka.
Další příklad
Opět pracujme s reálnou projektivní rovinu P2(R).
Uvažme nyní mnohočlen F2(x, y, z) = x3 + xz2 − y2z a příslušnou
kubickou křivku
C2 = {[x, y, z] ∈ P2
(R); F2(x, y, z) = 0}.
Hledejme singulární body na C2. Platí
∂F2
∂x
= 3x2
+ z2
,
∂F2
∂y
= −2yz,
∂F2
∂z
= 2xz − y2
.
Z ∂F2
∂x = 0 plyne x = 0 a z = 0, pak ale z ∂F2
∂z = 0 plyne i y = 0.
Ale trojice nul nedává žádný bod projektivní roviny. Singulární bod
na C2 tedy neexistuje a proto C2 není singulární křivka.
Eliptické křivky
Definice. Eliptická křivka nad tělesem K je uspořádaná dvojice
(E, O), kde E je nesingulární kubická křivka v P2(K) a O ∈ E.
Poznámka. Je možné zavést pojem biracionální ekvivalence dvou
křivek, spočívající v tom, že existují transformace prostoru
převádějící jednu křivku na druhou a obráceně, přičemž tyto
transformace jsou „pěkné v tom smyslu, že transformační rovnice
jsou dány homogenními polynomy téhož stupně nad K.
Věta. Libovolná eliptická křivka nad K je biracionálně ekvivalentní
s nějakou eliptickou křivkou (E, O) následujícího tvaru (přičemž
transformace převádějí vyznačený bod jedné křivky na vyznačený
bod druhé křivky)
E = {[x, y, z] ∈ P2
(K); F(x, y, z) = 0},
kde
F(x, y, z) = y2
z + a1xyz + a2yz2
− x3
− a3x2
z − a4xz2
− a5z3
,
a1, . . . , a5 ∈ K a O = [0, 1, 0].
Eliptické křivky dané Weierstrassovou rovnicí
V projektivní rovině zvolme za afinní část množinu těch bodů,
které mají nenulovou třetí souřadnici, tedy bodů [x, y, 1].
Každá eliptická křivka ve tvaru z předchozí věty má jeden nevlastní
bod (totiž O = [0, 1, 0]) a v afinní části je dána rovnicí
y2
+ a1xy + a2y = x3
+ a3x2
+ a4x + a5.
Tato rovnice se nazývá Weierstrassova rovnice.
V dalším textu budeme předpokládat, že charakteristika tělesa K
není ani 2 ani 3, tj. že 2 i 3 jsou invertibilní prvky v K.
Důvodem je to, že pro naše účely eliptické křivky nad tělesy
charakteristiky 2 a 3 nejsou zapotřebí a že tento předpoklad dále
zjednodušuje Weierstrassovu rovnici.
Můžeme pak totiž předpokládat, že a1 = a2 = a3 = 0, a tedy
Weierstrassova rovnice je tvaru y2 = x3 + a4x + a5.
Kdy Weierstrassova rovnice zadává eliptickou křivku?
Věta. Nechť K je těleso charakteristiky různé od 2 a 3, a, b ∈ K.
Rovnice y2 = x3 + ax + b je Weierstrassovou rovnicí nějaké
eliptické křivky, právě když platí 4a3 + 27b2 = 0.
Důkaz. Položme F(x, y, z) = y2z − x3 − axz2 − bz3. Platí
∂F
∂x
= −3x2
− az2
,
∂F
∂y
= 2yz,
∂F
∂z
= y2
− 2axz − 3bz2
.
Předpokládejme, že [x, y, z] je singulární bod. Pak z = 0 implikuje
x = y = 0, spor. Je tedy z = 0. Proto y = 0 a pro γ = x
z platí
3γ2 = −a, 2aγ = −3b. Jestliže a = 0, pak také b = 0. Naopak pro
a = b = 0 je bod [0, 0, 1] singulární. Zabývejme se dále případem
a = 0. Platí γ = −3b
2a , γ2 = −a
3 = 9b2
4a2 , tj. 4a3 + 27b2 = 0. Naopak,
je-li 4a3 + 27b2 = 0, a = 0, ověřme, že pro γ = −3b
2a je [γ, 0, 1]
singulární bod, což je snadné, například γ2 = 9b2
4a2 = −a
3, dále
γ3
+ aγ + b = −3b
2a −a
3 + a −3b
2a + b = b
2 − 3b
2 + b = 0.