Farkas Gábor Kátai Imre
Algebrai Geometriai Számítások
Egyetemi jegyzet
Budapest, 2012
2
Tartalomjegyzék 1. Bevezetés 1.1.
7
Köszönetnyilvánítás
. . . . . . . . . . . . . . . . . . . . . . . . .
2. Csoportelmélet
11
2.1.
Véges csoportok szerkezete
2.2.
Redukált maradékosztályok csoportja . . . . . . . . . . . . . . . .
2.3.
9
. . . . . . . . . . . . . . . . . . . . .
Z∗p -ban
. . . . . . . . . . . . . . . . . . .
2.2.1.
Primitív gyökök
2.2.2.
Diszkrét logaritmus probléma
2.2.3.
∗ Karakterek Zm -ban
Z∗p
14 15
. . . . . . . . . .
16
. . . . . . . . . . . . . . . . . . . . .
17
Kriptográ ai alkalmazások . . . . . . . . . . . . . . . . . . . . . .
21
2.3.1.
Diszkrét logaritmus általános ciklikus csoport esetén . . .
23
2.3.2.
A Pollard féle
2.3.3.
A PohlingHellman módszer
ρ
és
λ
esetén
11
módszer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3. Kvadratikus kongruenciák
23 25
27
3.1.
Legendre-szimbólum
. . . . . . . . . . . . . . . . . . . . . . . . .
3.2.
Jacobi-szimbólum . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
3.2.1.
31
A Jacobi-szimbólum kiszámítása
. . . . . . . . . . . . . .
4. Testek 4.1.
4.2.
27
35
Testb®vítések . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
4.1.1.
Minimálpolinom
39
4.1.2.
Algebrai testb®vítések . . . . . . . . . . . . . . . . . . . .
41
Véges testek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
. . . . . . . . . . . . . . . . . . . . . . .
3
4
TARTALOMJEGYZÉK
5. Kvadratikus testek
43
5.1.
Algebrai egészek kvadratikus testekben . . . . . . . . . . . . . . .
44
5.2.
Kvadratikus testek egységei
. . . . . . . . . . . . . . . . . . . . .
45
. . . . . . . . . . . . . . . . . . . . . . . . . .
47
5.3.
Kvadratikus formák és alapdiszkrimináns
5.4.
Ideálosztályszám
5.2.1.
Alapegység
. . . . . . . . . . . . .
49
. . . . . . . . . . . . . . . . . . . . . . . . . . .
51
6. Prímszámok
55
6.1.
Prímszámok eloszlása
6.2.
Riemann sejtései
. . . . . . . . . . . . . . . . . . . . . . . .
57
. . . . . . . . . . . . . . . . . . . . . . . . . . .
60
7. Szita algoritmusok
67
8. Prímtesztek 8.1.
69
Valószín¶ségi prímtesztek, pszeudoprímek
. . . . . . . . . . . . .
9. Prímrekordok
75
9.1.
A prímkeresés vázlata
9.2.
A paraméterek választása
9.3.
72
. . . . . . . . . . . . . . . . . . . . . . . .
77
. . . . . . . . . . . . . . . . . . . . . .
79
9.2.1.
A kandidátusok halmazának meghatározása . . . . . . . .
80
9.2.2.
A Riesel-teszt . . . . . . . . . . . . . . . . . . . . . . . . .
82
elejtett Sophie Germain és ikerprímek várható száma . . . .
84
Az
9.4.
A szitálás részletei
. . . . . . . . . . . . . . . . . . . . . . . . . .
87
9.5.
A szitálás hatékonyságának elemzése . . . . . . . . . . . . . . . .
89
10.Elliptikus görbék
93
10.1. Alapgondolatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.1.1. Csoport törvény
. . . . . . . . . . . . . . . . . . . . . . .
10.1.2. Projektív koordináták 10.1.3. Elliptikus görbék 10.2. Torziós pontok
. . . . . . . . . . . . . . . . . . . .
(mod n)
93 94 99
. . . . . . . . . . . . . . . . . 102
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
10.3. Elliptikus görbék véges test felett . . . . . . . . . . . . . . . . . . 105 10.4. Prímtfaktorizáció elliptikus görbékkel . . . . . . . . . . . . . . . . 106 10.5. Prímtesztelés elliptikus görbékkel . . . . . . . . . . . . . . . . . . 114
Irodalomjegyzék
124
TARTALOMJEGYZÉK
Tárgymutató
5
130
6
TARTALOMJEGYZÉK
1. fejezet
Bevezetés Ezt a jegyzetet azoknak ajánljuk, akik mélyebben akarnak foglalkozni a számítógépes számelmélettel. Itt els®sorban a a
prímfaktorizáció
prímtesztelésre
gondolunk, de érintjük
témakörét is. El®bbi probléma adott pozitív egész prímsé-
gének megállapításáról és annak bizonyításáról szól, utóbbi esetén pozitív egészek prímtényez®s felbontását keressük. Mindkét terület fontos szerepet játszik, nem csak a számelméletben, hanem bizonyos informatikai területeken is, mint például a
kriptográ a ,
amely rejtjelezéssel, titkosírással, illetve kódolásokkal
foglalkozó tudományág. A prímtulajdonság eldöntése nem lis alakú számok, például a
2n − 1
egyszer¶ kérdés. Vannak olyan speciá alakúak, amelyekre egyszer¶en eldönthet®,
prímszámok, vagy sem. Ilyen típusú számok között találhatunk néhány 10 000 000-nál több számjegy¶ bizonyítottan prím számot. A prímteszt elvégzése tetsz®leges (azaz nem speciális alakú) számokon pár ezer számjegy esetén már nehézséget okoz egy átlagos teljesítmény¶ számítógépen, még a legmodernebb komputeralgebrai szoftverek (Maple, Derive, Mathematica, stb) segítségével is. Érdekességként megjegyezzük, hogy a 2012 májusában legnagyobb ismert prímet 2008 agusztusában
találta Edson Smith ([15]):
x = 243112609 − 1. p
x egy úgynevezett Mersenne-prím (2
−1
alakú szám, ahol
p ∈ P)
és 12 978
189 jegy¶. További érdekesség, hogy majdnem egy évig azt sejtették a matema7
8
FEJEZET 1.
BEVEZETÉS
tikusok, hogy x a 46. Mersenne-prím, de 2009-ben találtak egy kisebbet, amely
pusztán 12 837 064 jegy¶. Felmerül tehát a kérdés, hogy hogyan lehet tökéletesíteni a prímteszteket. A
cél az, hogy olyan algoritmust alkossunk meg, amely implementálható, "gyorsan fut" és nincs nagy tárigénye. Ez a terület jó példája a matematika és informatika együttm¶ködésének. Vannak azonban olyan kiváló matematikai eredmények, amelyek egyel®re még a gyakorlatban nem használhatóak. Például Agrawal, Kayal és Saxena a 2000-es évek elején adtak egy olyan prímtesztel® algoritmust, amelyr®l bizonyították, hogy várható futási ideje az input bitekben mért hosszának polinomiális függvényével becsülhet®, azaz a prímszámok halmaza a P nyelvosztályba tartozik. Ezzel elméleti úton támogatták, azt a törekvést, hogy minél gyorsabb prímtesztel® programokat tudjunk írni, de az úgynevezett AKS-algoritmus számítógépes implementációja, f®leg az óriási tárigény miatt, még nem t¶nik járható útnak. Természetes módon adódik a kérdés, hogy a címben említett területeknek mi köze van az amúgy a számelmélethez sorolt prímteszteléshez. 2012-ben a prímteszt végrehajtásását elvégz® algoritmusok közül az úgynevezett
ECPP
(Elliptic Curve Primality Proving), azaz elliptikus görbés prímteszt, a leghatékonyabb. Itt központi szerepet játszanak az algebrai geometriában jól ismert elliptikus görbék. Ezek segítségével tudunk olyan csoportokat konstruálni, amelyek rendjét felhasználjuk a prímtulajdonság bizonyítására. Tehát az ECPP elméletének sikeres megértéséhez szükségünk van algebrai alapismeretekre is. Különös gyelmet kell szentelnünk a kvadratikus testeknek, mivel ezen algebrai stuktúrák algebrai egészeinek fontos szerepe van az ECPP elméletében, s®t a szintén egzakt prímtesztnek számító Riesel-tesztben is, amely Sophie Germain, illetve ikerprímek
vadászatánál használunk. A számelmélet bizonyos részeit is érintenünk kell, hiszen a prímszámok vizs-
gálatához szükségünk lesz olyan fogalmakra, eredményekre, amelyek közt van több száz éves, mégsem része a legtöbb fels®oktatási intézmény diszkrét matematika anyagának. Bizonyos de níciók és tételek magyarázata, bizonyítása szerepel a legtöbb informatikát oktató egyetem, vagy f®iskola BSc-s tematikáiban. Amennyiben valaki mégis ismeretlen fogalommal találkozna jegyzetünkben, akkor azt jó eséllyel megtalálja [58] könyvben. Néhány tétel bizonyítása is megtalálható itt, amelyek közlését®l jelen m¶ben eltekintünk.
1.1. KÖSZÖNETNYILVÁNÍTÁS
9
Összefoglalva ez a jegyzet olyan anyagot tartalmaz, amely egyrészt felhasználható a prímtesztelés és prímfaktorizáció elméletében felmerül® problémák, másrészt az elliptikus görbék elméletének alpavet® kérdéseinek megértéséhez.
1.1.
Köszönetnyilvánítás
Ezúton mondunk köszönetet a TÁMOP pályázatnak, amely projekt az Európai Unió támogatásával és az Európai Szociális Alap társ nanszírozásával valósul meg, a támogatási szerz®dés száma: TÁMOP 4.2.1/B-09/1/KMR-2010-0003.
10
FEJEZET 1.
BEVEZETÉS
2. fejezet
Csoportelmélet Elliptikus görbék pontjain de niált összeadási m¶velettel véges kommutatív csoportot kapunk. E csoportokat felhasználhatjuk faktorizációra, prímtesztelésre, és kriptográ ai célokra is. Ezért hasznos lehet a következ® néhány véges csoportok szerkezetével kapcsolatos fogalom.
2.1. Jelölje
Véges csoportok szerkezete |A|
a véges
értelmében, ha
B
A
csoport rendjét (azaz elemeinek számát). A Lagrange-tétel
részcsoport
A-ban,
akkor
|B|
osztója
|A|-nak.
Tetsz®leges (multiplikatív írásmódot alkalmazva) csoportban az
a∈A
elem
hatványai, azaz
. . . , a−3 , a−2 , a−1 , ε = a0 , a, a2 , . . . vagy mind különböz®ek, vagy nem, s az utóbbi esetben ezek az
Ua = {a, a2 , . . . , an−1 , an = ε} halmazból kerülnek ki, ahol
ε
a csoport egységeleme. Ha
egész ezzel a tulajdonsággal, akkor az számot az
a
(részcsoport
Ua
elem rendjének nevezzük, és
A-ban),
hiszen
an = ε
inverze
ak
−1
miatt
a legkisebb pozitív
n |a|-val jelöljük. Ua nyilván csoport ak · al = a(k+l) (mod n) , továbbá ak
= an−k ∈ Ua . 11
n
halmazban nincs ismétl®dés. Az
12
FEJEZET 2.
Világos, hogy
|a|
osztója
|A|-nak.
CSOPORTELMÉLET
Az egy elem által generált csoportot (van
ciklikus csoportnak generáló eleme (generátora). Természe-
olyan elem, amely hatványaival el®állítja az összes többit) nevezzük. Az tesen
Ua
a
Ua
elem az
csoport
generálható más, alkalmas elemével is. Az
generálja az
Ua
ah ∈ Ua
akkor és csak akkor
csoportot, ha az
{ah , a2h , . . . , anh = ε} al1 h 6= al2 h , ha 1 ≤ l1 ≤ l2 ≤ n, ami (h, n) = 1 (relatív prímek). Érvényes tehát a
elemek valamennyien különböz®k, azaz akkor és csak akkor teljesül, ha következ® állítás:
2.1. tétel.
Az
ah
elem akkor és csak akkor generálja az
(h, n) = 1. Ua -nak ϕ(n) ϕ(n)
Ua
az Euler-féle függvény, amely az
n-nél
nem kisebb, hozzá relatív prímek
számát adja. Vegyük észre, hogy ez pontosan azt jelenti, hogy egy ciklikus csoportban
ϕ(n)
darab
n-rend¶
b ∈ Ua
elem akkor lesz
d-rend¶,
b = ah , hd ≡ 0 Tehát
n
minden
d
osztójára
|a| = |Ua | = n.
ha
(mod n)
ϕ(n/d)
n elem¶ véges
elem van.
Folytassuk tovább a gondolatmenetet, és tegyük fel, hogy Egy
csoportot, ha
számú különböz® generáló eleme van.
darab
és
h,
d-rend¶
n = 1. d elem van. Így eljutottunk a
következ® állításhoz:
2.2. lemma.
Bármely
n ∈ N+
számra
X
ϕ(d) = n.
d|n
Bizonyítás: Tekintsük a következ®
n
darab tört számot:
n 1 2 , ,..., . n n n Mindegyik törtnél végezzük el az egyszer¶sítést, azaz minden törtet hozzunk
k/d
alakra, ahol
k
és
d
relatív prímek. Nyilvánvaló, hogy
fordul a nevez®kben és minden nevez®
n
osztója, továbbá
n összes osztója el®n/n = 1 kivételével a
2.1. VÉGES CSOPORTOK SZERKEZETE
13
számláló kisebb a nevez®nél. Számoljuk meg adott
d-re, hogy hányszor fordul el®
k érték szerepel számlálóként a sorozatban, amely (d, k) = 1. Ez pedig de níció szerint pontosan ϕ(d). n
nevez®ként, azaz hány olyan
d-nél
nem nagyobb és
összes osztójára összegezve minden törtet pontosan egyszer számolunk meg a sorozatban.
2.3. de níció.
Azt mondjuk, hogy valamely
részcsoportjainak
c∈C
direkt szorzata,
a = bc B1 , B2 , . . . , Bk
tartozik úgy, hogy
A
Hasonlóan,
a
A
ha minden
B és C b ∈ B és
kommutatív csoport a
a ∈ A-hoz
egyetlen
teljesül.
a∈A bj ∈ Bj és
részcsoportok direkt szorzata, ha minden
elemet pontosan egyféleképpen írhatunk
a = b1 . . . bk
alakban, ahol
(j = 1, . . . , k). A = BC (vagy A = B × C ), A = B1 × B2 × · · · × Bk ) jelölést.
A továbbiakban használjuk az
B1 B2 . . . Bk
( vagy
illetve az
A=
A csoportelméletben alapvet® fontosságúak a következ® állítások.
2.4. lemma.
Legyen
A egy N -rend¶ kommutatív csoport, |A| = N , N = N1 N2 ,
(N1 , N2 ) = 1, E1 = {α ∈ A : |α| | N1 }, E2 = {β ∈ A : |β| | N2 }. Ekkor
E1 , E2
részcsoport
A-ban,
Bizonyítás: Nyilvánvaló, hogy
γ ∈ A.
és
E1 E2 = A.
E1 , E2
csoport és az is, hogy
E1 E2 ⊆ A.
Legyen
Az
1 = N1 u1 + N2 u2 egyenlet alkalmas egészekkel megoldható (az euklidészi-algoritmus következménye), ezért
γ
felírható a következ® alakban:
γ = γ N1 Legyen
ζ = γ N1
u1
elemre teljesül, hogy
u 1
· γ N2
u2
.
u 2 ξ = γ N2 . Ekkor ζ N2 = ξ N1 = ε, mivel minden δ ∈ A δ N = ε. Végül a felbontás egyértelm¶ségét látjuk be.
és
Tegyük fel indirekt módon, hogy az
α = ξ1 ζ2 = ξ2 ζ1
14
FEJEZET 2.
CSOPORTELMÉLET
egyenlet megoldható nem triviálisan, azaz úgy, hogy
ξ1 , ξ2 ∈ E1 , ζ1 , ζ2 ∈ E2 , ξ1 6= ξ2 . Ekkor
ξ1 ξ2−1 = ζ1 ζ2−1 ,
és így
γ = ξ1 ξ2−1 -re γ 6= ε, γ ∈ E1 ∩ E2
teljesül, így
kapjuk az
|γ| | N1 , |γ| | N2 , |γ| | (N1 , N2 ) = 1, összefüggéseket. Tehát
|γ| = 1,
ami azt jelenti, hogy
γ = ε,
ez pedig ellentmond
indirekt feltételünknek, azaz a felbontás egyértelm¶, amivel a lemmát bizonyítottuk.
2.5. lemma. ahol
α
A egy N -rend¶ kommutatív csoport, és N = P1 P2 . . . Pr , p1 , . . . , pr különböz® prímek. Legyen továbbá
Legyen
Pj = pj j ,
és
Ej = {α ∈ A | |α| | Pj }, (j = 1, . . . , r). Ekkor
A = E1 E2 . . . Er .
A bizonyítás az el®z® lemmából,
r-szerinti
teljes indukcióval következik, ennek
részletes leírásától eltekintünk.
2.2. Adott
Redukált maradékosztályok csoportja m 6= 0
egészre jelölje
csoportját, azaz legyen
Z∗m
a
redukált maradékosztályok multiplikatív
Z∗m = {a (mod m) | (a, m) = 1}. Világos, hogy
1 (mod m) ∈
Z∗m
csoport, ugyanis
Z∗m , és
(a, m) = 1, (b, m) = 1 esetén (ab, m) = 1,
aϕ(m)−1 ≡ a−1
A kínai maradéktételb®l, továbbá a
2.5
(mod m).
lemmából következik, hogy
Z∗m = Z∗pa1 × · · · × Z∗par r , 1
ha
m
törzstényez®s felbontása
2.6. lemma.
Ha
p>2
m = p1a1 . . . par r .
prímszám, akkor
Z∗pα
ciklikus csoport.
2.2. REDUKÁLT MARADÉKOSZTÁLYOK CSOPORTJA
Bizonyítás: Tudjuk, hogy az állítás igaz, ha
α = 1.
15
Legyen most
α = 2.
(g + p)p−1 = g p−1 + (p − 1)pg p−2 + · · · + pp−1 ≡ g p−1 + (p − 1)pg p−2
Mivel
(mod p2 ),
teljesül, ezért vagy
g p−1 6≡ 1
(mod p2 ),
vagy
(g + p)p−1 6≡ 1
(mod p2 )
g , vagy (g + p) rendje biztosan ϕ(p2 ), ezért g , vagy (g + p) primitív (mod p ). Indukcióval, tegyük fel, hogy
fennáll, tehát gyök
2
ϕ(pα−1 )
g0
6≡ 1
(mod pα ).
Az EulerFermat tétel szerint
ϕ(pα−1 )
g0 alkalmas
t-vel,
ϕ(pα ) g0
ahol
= (1 + tp
teljesül, tehát
p - t.
= 1 + tpα−1
Ezért
p ) = 1 + tp + (p − 1)t2 p2α−2 + · · · + tp pp(α−1) 2
α−1 p
ϕ(pα )
g0
α
≡ 1 + tpα 6≡ 1
(mod pα+1 ).
Ez az állítás általánosítható:
2.7. tétel.
Véges kommutatív csoport prímhatványrend¶ ciklikus csoportok di-
rekt szorzata. Ez az eredmény
véges kommutatív csoportok alaptétele néven vált ismertté,
bizonyítása [59] könyvben található.
2.2.1.
Primitív gyökök Z∗p -ban
p prímszámra Zp test, és Z∗p = Zp \ {0}, mint ahogy ∗ ∗ láttuk, Zp ciklikus csoport. Létezik tehát olyan g ∈ Zp elem,
Mivel
Z∗p = {g, g 2 , . . . , g p−1 }.
azt az el®z®ekben amelyre
16
FEJEZET 2.
Az ilyen
g
generáló elemet a számelméletben
Adott g (mod p − 1)
primitív gyök és
primitív gyöknek
Z∗p esetén jelölje
y ∈
nevezzük.
ind(y) = indg (y)
azt a
meghatározott egész számot, amelyre
g ind(y) ≡ y
(mod p).
neve y g alapú (g szerinti) indexe . véges logaritmus kifejezés is.
indg (y) a
CSOPORTELMÉLET
Használatos még index helyett
Világos, hogy
ind(y1 y2 ) ≡ ind(y1 ) + ind(y2 )
(mod p − 1),
valamint
ind(1) ≡ 0 és így az
y 7→ ind(y)
függvény
Z∗p -ot
a
(mod p − 1), Zp−1 -re
leképez® lineáris függvény, tehát
izomor zmus.
g (mod p), akkor a többi primitív gyököt nagyon h egyszer¶en meghatározhatjuk. Legyen gh = g . Ahhoz, hogy gh primitív gyök ν legyen, szükséges és elégséges feltétel, hogy gh rendje p − 1, azaz gh = 1 nem ν teljesül egyetlen 1 ≤ ν < p − 1 esetén sem. Mivel gh = 1 akkor teljesül, ha Ha adott egy primitív gyök,
ν·h≡0 ezért
(h, p − 1) = 1
esetén
gh
(mod p − 1),
Következményként megállapíthatjuk,
ϕ(p − 1)
2.2.2. A
(h, p − 1) > 1 esetén nem. hogy adott p prímszámhoz pontosan
primitív gyök,
számú különböz® primitív gyök létezik.
Diszkrét logaritmus probléma Z∗p esetén
diszkrét logaritmus probléma
általában azt jelenti, hogy egy hatványozás
eredményét és alapját ismerve szeretnénk a kitev®t meghatározni. Mivel ez a redukált maradékosztályok multiplikatív csoportjában nem könny¶ feladat, ezért ∗ kriptográ ai alkalmazásoknál is használható. Legyen most a, b ∈ Zp , keresend® az a
k
egész, amellyel
ak = b
fennáll. A kis Fermat-tétel értelmében
ap−1 = 1
(mod p),
2.2. REDUKÁLT MARADÉKOSZTÁLYOK CSOPORTJA
17
ap−1 = 1 Z∗p -en, ezért ha k = k1 megoldás, akkor k2 ≡ k1 (mod p − 1) esetén k = k2 is megoldás. Nem biztos, hogy mindig van megoldás. Legyen g ind(a) primitív gyök. Az a = g és b = ind(b) jelöléssel az egyenlet ekvivalens a azaz
k · ind(a) ≡ ind(b)
(mod p − 1)
kongruenciával. Mint azt tudjuk ennek a lineáris kongruenciának akkor és csak akkor van megoldása, ha
(p − 1, ind(a)) | ind(b) teljesül. Könnyen látható, hogy ha
a (mod p)
primitív gyök, akkor mindig van
megoldás, ugyanis ekkor
(p − 1, ind(a)) = 1 fennáll.
2.2.3.
Karakterek Z∗m -ban
El®ször általánosságban tisztázzuk a karakter fogalmát. Legyen
G
véges kom-
|G| = N . Jelölje T az egységnyi abszolútérték¶ komplex KN az N -edik komplex egységgyökök halamzát. A χ : G −→ T függvényt a G karakterének nevezzük, ha
mutatív csoport, és
számok halmazát, továbbá
χ(ab) = χ(a)χ(b),
(2.1)
a, b ∈ G esetén teljesül. Jelölje XG a G csoport karaktereinek halmazát. Vegyük észre, hogy XG nem üres, hiszen a minden a ∈ G-re χ(a) = 1-et adó függvény nyilvánvalóan karakter. Ezt a karaktert χ0 -lal jelöljük és f®karakternek nevezzük. Igaz az is, hogy χ1 , χ2 ∈ XG esetén χ1 · χ2 ∈ XG is fennáll, mivel χ1 χ2 (a) = χ1 (a) · χ2 (a). Továbbá χ ∈ XG esetén χ is eleme XG -nek, ahol χ(a) := χ(a), és a felülvonás a komplex konjugáltat jelenti. Világos tehát, hogy XG csoportot alkot a függvényszorzás m¶veletével. Tudjuk továbbá, hogy χ0 az egységelem, és tetsz®leges χ elem inverze χ. minden
2.8. de níció.
XG
a
G
karaktereinek csoportja.
18
FEJEZET 2.
CSOPORTELMÉLET
G karakterei hogyan függnek G rendjét®l, azaz N t®l. Ha e a G, 1 pedig az XG csoport egységeleme, akkor e = e · e, amib®l χ(e) = χ(e) · χ(e) következik, és innen χ(e) = 1 adódik. Továbbá Most nézzük meg, hogy
aN = e miatt
χ
értékei
és
1 = χ(e) = χ(aN ) = χ(a)N
KN beliek, azaz N -edik egységgyökök. G egy N -edrend¶ véges ciklikus csoport,
Legyen most
tehát alkalmas
a∈G
elemmel:
G = a, a2 , . . . , aN −1 , aN = e . Legyen továbbá
ξ
tetsz®leges
N -edik
komplex egységgyök, és legyen
χξ (aj ) = ξ j (j = 1, 2, . . . , N ). Nyilvánvaló, hogy
χξ
karakter, hiszen
b = ai , c = aj
χξ (b) · χξ (c) = χξ (ai ) · χξ (aj ) = ξ i+j = ξ i+j Észrevehetjük, hogy ezzel
G
esetén
(mod N )
= χξ (bc).
összes karakterét megadtuk. Másrészt
ξ1 , ξ2 ∈ KN
esetén
χ ξ1 ξ2 = χ ξ1 χ ξ2 , amib®l rögtön következik, hogy következik, hogy
2.9. lemma. A
és
B
G
XG
és
Legyen
G
XG
ciklikus csoport és
|XG | = N .
Ebb®l az is
izomorfak.
véges multiplikatív csoport,
G = AB
a
G
felbontása az
részcsoportok direkt szorzatára.
χA ∈ XA , χB ∈ XB , és az f : G → C függvényt értelmezzük a g ∈ G, g = a · b, a ∈ A, b ∈ B , akkor legyen f (g) = χA (a)χB (b). Ekkor állítjuk, hogy f ∈ XG . (ii) Legyen χG ∈ XG g = χG | χA a χG megszorítása az A halmazra, azaz g(a) = χG (a) minden a ∈ A-ra. Ekkor g ∈ XA . (iii) Az XG az XA és XB részcsoportok direkt szorzata. |G| (iv) χ(g) = 1 minden g ∈ G-re. (i) Legyen
következ® módon: ha
(ii) állítások nyilvánvalóan igazak, a (iii) ezekb®l közvetlenül következik. (iv) belátásához tekintsük az e ∈ G egységelemet, amelyre χ(e2 ) = χ(e) = χ(e)χ(e) fennáll, továbbá χ(e) = 1, és g |G| = e miatt teljesül az Bizonyítás:
Az
(i)
és
1 = χ(g |G| ) = χ(g)|G|
2.2. REDUKÁLT MARADÉKOSZTÁLYOK CSOPORTJA
19
egyenl®ség. Tekintsük most a következ® összeget:
Sχ :=
X
χ(a) .
a∈G Mivel minden
b∈G
esetén
Sχ =
X
χ(a) =
a∈G
X
χ(ab) = χ(b) · Sχ
a∈G
fennáll, ezért két esetet kell megkülönböztetnünk. Amikor minden
χ(a) = 1,
azaz
χ
Sχ =
a ∈ G-re
f®karakter, illetve amikor nem az. Tehát kapjuk, hogy
X
χ(a) =
a∈G De niáljuk most
a ∈ G-re
|G| , 0,
ha ha
χ χ
f®karakter, nem f®karakter.
(2.2)
az
X
R(a) :=
χ(a)
χ∈XG összeget. Legyen továbbá
ψ ∈ XG ,
amely hasonló szerepet játszik, mint
el®z® esetben. Tehát futtassuk végig
χ-t
és
ψ -t G
b
az
elemein egyszeresen, ekkor
kapjuk, hogy
X
R(a) =
ψ(a)χ(a) = ψ(a) · R(a).
ψχ∈XG
a 6= e, ahol e a G egységeleme, akkor van a = 1, akkor minden ψ esetén ψ(a) = 1, tehát
Ismét két esetet kell vizsgálni. Ha olyan
ψ,
amelyre
ψ(a) 6= 1.
Ha
megállapíthatjuk, hogy
R(a) =
X χ∈XG
Z∗m
karaktereit
χ(a) =
|G| , 0,
Dirichlet karaktereknek
ha ha
a = e, a 6= e.
nevezzük. Legyen
αr 1 m = 2α0 pα 1 . . . , pr ,
(2.3)
20
FEJEZET 2.
CSOPORTELMÉLET
p1 , p2 , . . . , pr különböz® páratlan prímszámok. Szeretnénk meghatározni ∗ Zm karaktereit. Mivel az el®z®ekben láttuk, hogy
ahol
Z∗m = Z∗2α0 × Z∗pα1 × . . . , ×Z∗pαr r , 1
ezért elegend® azokat az eseteket vizsgálni, amikor
m
prímhatvány.
1. eset: m 2 hatvány. Z∗2 = {1 (mod 2)}, ezért χ(1 (mod 2)) = 1 az egyetlen = {1 (mod 4), 3 (mod 4)} esetén két karakter van, mivel χ0 (1 (mod 4)) = 1 = χ0 (3 (mod 4)), χ1 (1 (mod 4)) = 1, vagy χ1 (3 (mod 4)) = 3. Mivel
karakter.
Z∗4
α > 2, ekkor Z∗2α nem ciklikus csoport, hanem egy másodrend¶ és egy α − 2-edrend¶ csoport direkt szorzata. Egyzer¶en α ∗ γ γ beláthatjuk, hogy minden h (mod 2 ) ∈ Z2α egyértelm¶en írható h ≡ (−1) 5 0 α 2α−2 γ (mod 2 ) alakban. Legyen e ∈ {−1, 1}, e0 = 1, és ψe,e0 (h) = e · eγ0 , ∗ ∗ valamely h ∈ Z2α -ra. Az ilyen módon el®állított ψe,e0 függvények adják Z2α Legyen most
m = 2α ,
ahol
összes karakterét.
2. eset: m = pα , ahol p páratlan. Tudjuk, hogy
Z∗p
Z∗pα is h ∈ Z∗pα
ciklikus csoport, amib®l könnyen belátható, hogy
g generáló elem Z∗pα -ban, azaz minden µ(h) α felírható g hatványaként: h = g , ahol µ(h) (mod ϕ(p )) van meghatározva. µ(h) α Legyen most ξ ∈ Kϕ(pα ) és χ(h) = ξ . Ekkor χ karakter (mod p ), és ciklikus csoport. Ekkor létezik
minden karakter el®áll alkalmas
ξ
választással.
Valamely Dirichlet karaktert kiterjeszthetünk az egész számokon értelmezett függvénnyé a következ® módszer segítségével. Adott
χ(n) :=
(mod m)),
ha ha
legyen
n (mod m) ∈ Z∗m , (n, m) > 1.
χ(n) (mod m) periodikus, továbbá multiplikatív χ(n1 n2 ) = χ(n1 )χ(n2 ), minden n1 , n2 ∈ Z esetén fennáll.
Világos, hogy azaz
χ(n 0,
m-re
(2.4) függvény,
A fejezet elején részletezett számolásokkal itt is el®állíthatók a következ® összegek:
2.3. KRIPTOGRÁFIAI ALKALMAZÁSOK
X
Sχ∗ = n
χ(n) =
(mod m)
ϕ(m), 0,
21
ha
χ χ
ha
a≡1
ha
f®karakter,
(2.5)
nem f®karakter,
valamint
R∗ (a) =
X
χ(a) =
χ∈XZ∗ m
ϕ(m), 0,
egyébként
(mod m), .
(2.6)
Megjegyezzük, hogy részben a Dirichlet-karakterek segítségével bizonyította Dirichlet a következ®, róla elnevezett, prímszámokkal kapcsolatos állítást:
2.10. tétel.
Legyen
k > 0, l
egészek és
(k, l) = 1. Ekkor az n+lk , l = 0, 1, 2, . . .
számtani sorozat végtelen sok prímet tartalmaz.
2.3.
Kriptográ ai alkalmazások
A diszkrét logaritmus problémát a
gyorshatványozás
módszerével viszonylag
könny¶ megoldani végtelen ciklikus csoportok esetén, ahol a generáló elem hatványai könnyen sorbarendezhet®k. Nehezebb a dolgunk véges csoportok esetén, ezért is alkalmaznak ilyen struktúrákat kriptográ ai rendszerekben. Tekintsük most a fent említett módszert, amelyet neveznek
ismételt hatványozásnak
a ∈ R, ahol R tetsz®leges egységelemes gy¶r¶, továbbá n kimenet a ∈ R. Írjuk fel a kitev®t kettes számrendszerben:
is. Az eljárás bemenete
n
pozitív egész, a
n = nk 2k + nk−1 2k−1 + · · · + n1 2 + n0 20 , ahol
nk = 1 ,
és
ni ∈ {0, 1},
számjegyekben mért hossza
ha (0 ≤ i ≤ k − 1). Ekkor tudjuk, hogy n k < log2 (n + 1). Igaz továbbá, hogy k
k−1
an = ank 2 · ank−1 2 Nincs más dolgunk, mint összeszorozni ®ket. Mivel
ni = 1
1
bináris
0
· . . . · an1 2 · an0 2 .
esetetekre el®állítani az
i−1 2 i a2 = a2 ,
i
ani 2
számokat, és
22
FEJEZET 2.
ezért az
a
elem
2i
kitev®j¶ hatványait el®állíthatjuk
ványok összeszorzásához is legfeljebb
k
k
CSOPORTELMÉLET
számú szorzással. A hat-
szorzást használunk, tehát a gyorshat-
ványozás m¶veleti igénye legfeljebb
2k < 2 · log2 (n + 1)) darab szorzás.
Repeatedsquare(a, n) 1 2 3 4 5 6
n = nk 2k + nk−1 2k−1 + · · · + n1 2 + n0 bk ← a for i = k − 1 to 0 step by -1 if ni = 1 then bi ← b2i+1 · a else bi ← b2i+1 return b0
2.11. példa.
Számoljuk ki
a17 -t. A kitev® kettes számrendszerben felírva
17 = 1 · 24 + 0 · 23 + 0 · 22 + 0 · 21 + 1 · 20 , amib®l az algoritmus szerint kapjuk, hogy
17
a
=
2 2 2
2 · a.
a
Ez számunkra 4 négyzetreemelést és egy szorzást jelent. De a négyzetreemelés is egy szorzás, tehát öt szorzással Most tegyük fel, hogy
R = Z11
és
a = 6.
megússzuk a számolást.
Véges testben méginkább leegy-
szer¶södik a számolásunk, hiszen
617 =
62
2 2
2 ·6≡
2
(3)
2 2
·6
(mod 11),
amib®l kapjuk, hogy
(−2)
2
2
2
· 6 ≡ (4) · 6 ≡ 5 · 6 ≡ 8
Így természetesen jócskán
(mod 11).
lefaragtuk a
617 = 16926659444736 szám és
11-gyel
való osztási maradékának kiszámolására fordított id®t.
2.3. KRIPTOGRÁFIAI ALKALMAZÁSOK
2.3.1.
23
Diszkrét logaritmus általános ciklikus csoport esetén
Röviden ismertetünk egy módszert, amely D. Shankst®l számazik. Tehát legyen
G
P ∈ G generáló elem, |G| = N , kP = Q fennáll (additív írásmódot
véges ciklikus csoport,
az a
k
egész, amellyel
(1) Rögzítsük valamely
√
m ≥
N
Q ∈ G.
és
Keresend®
használva).
számot, és számítsuk ki
mP
értékét. Ezt
megtehetjük például gyorsszorzással.
(2) Számítsuk ki és tároljuk az
iP (i = 0, . . . , m − 1)
elemeket.
(3) Számítsuk ki az
Rj := Q − j(mP ) elemeket
j = 0-tól
kezdeve
(j = 1, 2, . . . ), addig amíg Rj Rj = iP . Ekkor
az
lP
értékek valame-
lyike nem lesz. Tegyük fel, hogy
iP = Q − j(mP ),
azaz
Q = (jm + i)P ,
tehát
k = jm + i.
Nyílvánvaló, hogy ez az eljárás mindig m¶ködik, hátránya viszont, hogy a sok tárhelyet foglal (lásd (2) lépés).
2.3.2.
A Pollard féle ρ és λ módszer
G véges ciklikus csoport, |G| = N P, Q ∈ G. Keresend® az a k egész, kP = Q fennáll. Válasszunk egy f : G −→ G függvényt. Válasszunk továbbá egy P0 ∈ G elemet, és számítsuk ki a Pi+1 = f (Pi ) (i = 0, 1, . . . ) iteráltakat, amíg ismétl®dést nem kapunk. Legyen Pi0 = Pj0 , i0 < j0 . Ekkor
Legyen
amellyel
Pi0 +r = Pj0 +r (r ≥ 0). P √ √i prímperiódusa a(j0 − i0 ) valamely osztója. Megalapozott a remény, N -nél kevesebb iteráció során ismétl®dést kapunk, azaz j0 − i0 < N .
hogy Így a
tárolási igény kevesebb lesz, mint a Shanks módszernél. A tárolási igény lényegében lenullázható. Tegyük fel, hogy
Pj+hd = Pj+sd .
d a periódus, azaz
24
FEJEZET 2.
i = j + hd, és 2i = j + sd teljesül, i, amelyre Pi = P2i . Vegyük észre, hogy
Ekkor
CSOPORTELMÉLET
i = (s − h)d.
ha
Található tehát olyan
P2(i+1) = f (f (P2i )) , Pi+1 = f (Pi ) . Ez azt jelenti, hogy a
(Pi , P2i ) −→ Pi+1 , P2(i+1) iterációnál nem kell meg®rizni a
értékeket, ha megtaláltuk azt
Pi = P2i . f függvényt? Osszuk a G csoportot s darab, közel azonos számú elemet tartalmazó diszjunkt S1 , S2 , . . . , Ss részhalmazra. Válasszunk 2s darab, (mod N ) inkongruens elemet: ai , bi (i = 1, 2, . . . , N ). Legyen az
i
(Pt , P2t ) (t < i)
értéket, amelyre
Hogyan válasszuk meg az
Mi = ai P + bi Q, továbbá
f (g) := g + Mi , Legyenek
a0 , b0
véletlen számok
ha
(mod N )
g ∈ Si .
és
P0 = a0 P + b0 Q. Minden
j -re Pj = uj P + vj Q.
Jegyezzük meg az
(uj , vj )
koordinátákat. Ha
Pj = uj P vj Q
és
Pj ∈ Si ,
akkor
pj+1 = (uj + ai )P + (vj + bi )Q, ezért
(uj+1 , vj+1 ) = (uj , vj ) + (ai , bi ). Ha valamely
i0 < j0
esetén
Pi0 = Pj0 ,
akkor
uj0 P + vj0 Q = ui0 P + vi0 Q,
2.3. KRIPTOGRÁFIAI ALKALMAZÁSOK
25
s így
(ui0 − uj0 )P = (vj0 − vi0 )Q. Ha
(vj0 − vi0 , N ) = d,
akkor
k ≡ (vj0 − vi0 )−1 (ui0 − uj0 ) ahol
kd
(mod N/d),
darab különböz® szám egyike. Általábnan
d
nem túl nagy, tehát sorra
mindet kipróbáljuk. A most ismertetett eljárást nevezzük
szernek . A Polard-féle λ módszer tén egyetlen
f
az el®z® eljárás párhuzamosítása. Ekkor szin-
(1)
(2)
(r)
P0 , P0 , . . . , P0 különböz® ki(l) tudjuk számolni a Pj (l = 1, 2, . . . , r)
függvényt választunk, de több
induló pontot. Így több processzoron
j = 0, 1, . . .
Polard-féle ρ mód-
pontokat a
(l+1)
(l)
Pj
= f (Pj )
formulával. Egy központi processzor összehasonlítja a sorozatokat. Ha
(l )
Pj2 2
(l )
Pj 1 1 =
, akkor
(l )
(l )
Pj1 1+t = Pj2 2+t (t = 0, 1, 2, . . . ) is fennáll.
2.3.3. Legyen
A PohlingHellman módszer G
csoport és
P, Q ∈ G
olyan
k
egész számot keresünk, amelyre
teljesül. Tegyük fel továbbá, hogy ismerjük
P
rendjét,
|P | = N ,
és
N
kP = Q törzsté-
nyez®s felbontását:
N= A módszer lényege: határozzuk meg a
Y
qiei .
k (mod qiei ) értékeket, majd alkalmazzuk
a kínai maradéktételt. Legyen
k q -alapú
qe k N ,
azaz
qe
pontos prímhatvány osztója
N -nek.
Az (ismeretlen)
számrendszerben felírva legyen
k = k0 + k1 q+, . . . , ki ∈ {0, 1, . . . , q − 1}. Egymás után meghatározzuk a
k
k0 , k1 , . . . , kq−1
értékeket, amelyekb®l
(mod q e ) = k0 + k1 q + · · · + ke−1 q e−1
26
FEJEZET 2.
CSOPORTELMÉLET
adódik.
(1) El®állítjuk a következ® halmazt:
N T = j P | j = 0, 1, . . . , q − 1 . q (2) Kiszámoljuk az
(N/q)Q
értéket. Mivel
N Q = k0 q amivel
k0
(3) Ha
e=1
(N/q)Q ∈ T , N P , q
ezért
értékét meg is határoztuk.
(4) Legyen
megállunk, ha nem, akkor folytatjuk tovább.
Q1 := Q − k0 P .
(5) Kiszámoljuk az
(N/q 2 )Q1
értéket, amely eleme
(N/q 2 )Q1 = k1
N P q
T -nek,
ezért
.
Az eljárást folytatjuk. Megjegyezzük, hogy ez a módszer akkor hatékony, ha
N
prímtényez®i kicsik.
3. fejezet
Kvadratikus kongruenciák Ebben a fejezetben olyan fogalmakkal ismerkedhetünk meg, amelyek többek között prímtesztel® algoritmusoknál használatosak. Ismertnek tételezzük fel az oszthatóság, prímszám, felbonthatatlan, egység, asszociált de nícióját, továbbá a kis Fermat-tételt és a lineáris kongruenciákkal kapcsolatos alapkérdéseket. A fejezet egészében feltesszük, hogy minden említett szám egész, amennyiben másképp nem de niáljuk.
3.1.
Legendre-szimbólum
Tekintsünk el®ször egy speciális kongruenciát, ahol tulajdonképpen azt kérdezzük egy adott számról, hogy van-e gyöke egy prímszámrend¶ testben.
3.1. de níció.
Legyen
kus maradéknak
p>2
prím és
(a, p) = 1.
Ekkor az
a
számot
kvadrati-
nevezzük, ha megoldható az
x2 ≡ a (mod p) kongruencia, és
kvadratikus nemmaradéknak,
Vegyük észre, hogy
p = 2
esetén csak az
ha nem oldható meg.
a ≡ 1 (mod 2)
pedig kvadratikus maradék. Megjegyezzük továbbá, hogy az számokat egyik kategóriába sem soroljuk be. 27
fordulhat el®, ez
a ≡ 0 (mod p)
28
FEJEZET 3.
3.2. de níció. a p
vagy
p
Legyen
KVADRATIKUS KONGRUENCIÁK
Legendre-szimbólumot (a | p)-vel,
páratlan prím. A
-vel jelöljük, és a következ®képpen de niáljuk:
a 1, = −1, p
ha ha
a a
kvadratikus maradék
(mod p), (mod p).
kvadratikus nemmaradék
Eulert®l származik a következ® eredmény, amelyet
Euler-kritériumnak
is szoktak nevezni. A Legendre szimbólum e tulajdonságát, több valószín¶ségi prímtesztel® algoritmusnál is használhatjuk.
3.3. lemma (Euler).
Bármely
a Bizonyítás: Legyen
p−1 2
p > 2 prímre és 0 < a < p-re a ≡ (mod p). p
y = a(p−1)/2 .
Mivel
y 2 = ap−1 ≡ 1
(mod p),
y ∈ {−1, 1}. Ha a kvadratikus maradék, azaz a ≡ b2 (mod p), y ≡ bp−1 ≡ 1 (mod p), tehát p−1 a 2 (mod p) a ≡ p
ezért
akkor
teljesül. Ha
a
kvadratikus nemmaradék, akkor
a ≡ g ind(a)
és
(ind(a), 2) = 1,
követ-
kezésképpen
a
p−1 2
Mivel
≡ g ind(a)
p−1 2
(mod p).
p−1 6≡ 0 (mod p − 1), 2 y ≡ −1 = ap , amivel a bizonyítást
ind(a) ezért
y 6≡ 1 (mod p),
tehát
befejeztük.
Eddigi ismereteinkb®l közvetlenül következik az alábbi állítás, amelynek több fontos következménye is van.
3.4. lemma.
p > 2 prímszám és Z∗p generáló eleme g . a 1, ha indg (a) páros, = −1, ha indg (a) páratlan. p
Legyen
Ekkor
3.1. LEGENDRE-SZIMBÓLUM
3.5. következmény.
p>2
29
prímszámra
Z∗p -ban
a kvadratikus maradékok rész-
csoportot alkotnak, amelyek rendje
p−1 . 2
3.6. következmény.
p>2
prímszámra
Z∗p -ban
p−1 X a
p
a=1
3.7. következmény.
= 0.
a ≡ b (mod p) a b = . p p
p>2
prímszámra
esetén
3.8. következmény.
p > 2 prímszámra −1 1, ha p ≡ 1 (mod 4), = −1, ha p ≡ −1 (mod 4). p
3.9. következmény.
p>2
prímszámra
ab p
=
a b . p p
Bizonyítás: Tekintsük a következ® összefüggést, amelyben az Euler-lemmát alkalmazzuk kétszer:
ab p
≡ (ab)
p−1 2
= (a)
p−1 2
(b)
p−1 2
a b ≡ p p
(mod p).
A kongruencia de níciója szerint ekkor az
x= kifejezés egyrészt csak a
0
és
prímszámmal. Tehát csak az
ab p
−
a b p p
±2 értéket veheti fel, másrészt osztható a p > 2 x = 0 állhat fenn, amivel a lemmát igazoltuk.
30
FEJEZET 3.
p
Az is nyílvánvaló, hogy a
KVADRATIKUS KONGRUENCIÁK
modulussal de niált Legendre-szimbólum
Z∗p -on
értelmezett karakter. Most próbáljuk meg általánosítani a Legendre-szimbólum de nícióját. Tulajdonképpen
Z-n
értelmezett függvényt
csinálunk bel®le, vagyis a modulushoz nem relatív prímekre is értelmezzük. Tehát p > 2 prímre legyen
0, a = 1, p −1, p=2
ha ha ha
p | a, a kvadratikus a kvadratikus
(mod p), (mod p).
nemmaradék
esetén a Legendre-szimbólumot a következ® formulával értelmezzük:
a 2
3.2.
maradék
=
0, 1,
ha ha
2 | a, 2 - a.
Jacobi-szimbólum
Nagy számok prímtesztelésénél gyakran használjuk a Legendre-szimbólum általánosítását tetsz®leges egész számra:
3.10. de níció.
Legyen
m = p1 p2 . . . pn tetsz®leges páratlan egész, ahol a pi (a, m) = 1. Ekkor a következ® szorzatot
k nem feltétlenül különböz® prímek és
Jacobi-szimbólumnak
nevezzük:
a m
=
n Y a i=1
pi
.
A Jacobi-szimbólum de níciójából, továbbá a Legendre-szimbólum tárgyalásakor szerzett ismereteink alapján könnyen belátható az alábbi három állítás.
3.11. lemma.
Legyen
(1) (2) (3)
m, m0 > 2
tetsz®leges páratlan egész szám, ekkor
a
= a ≡ b (mod m) =⇒ m ab a b = , m m m a a a = . m m0 m · m0
b m
,
3.2. JACOBI-SZIMBÓLUM
31
A következ® segédtétel is könnyen belátható.
3.12. lemma.
Legyen
m, m0 > 2 tetsz®leges páratlan m−1 −1 = (−1) 2 . m
egész szám, ekkor
Bizonyítás: Az állítás bizonyításához felhasználjuk az Euler-kritériumot, tehát ha
m = p1 p2 . . . pn ,
akkor
−1 m
Vegyük észre, hogy páratlan
= (−1) t, s
p1 −1 2
. . . (−1)
m
.
esetén
st − 1 s−1 t−1 + ≡ 2 2 2 és mivel
pn −1 2
(mod 2),
páratlan, így prímfaktorai is, amib®l kapjuk, hogy
(−1)
p1 −1 2
(−1)
p2 −1 2
= (−1)
p1 p2 −1 2
.
Innen indukcióval könnyen igazolhatjuk a (4) állítást.
3.2.1.
A Jacobi-szimbólum kiszámítása
A Legendre-, illetve Jacobi-szimbólumot kiszámoló algoritmusoknál használható
kvadratikus reciprocitás törvénye, melynek els® (és számos további) bizonyítása Gausstól származik.
a következ® két eredmény. Utóbbi az úgynevezett
3.13. tétel.
Legyen
m = p1 p2 . . . pn
tetsz®leges páratlan egész, ahol a
feltétlenül különböz® prímek. Ekkor
2 m
= (−1)
m2 −1 8
.
A teljesség kedvéért megjegyezzük, hogy
2 m
= (−1)
m2 −1 8
=
1, −1,
ha ha
m ≡ ±1 (mod 8), m ≡ 3, 5 (mod 8).
pi -k
nem
32
FEJEZET 3.
KVADRATIKUS KONGRUENCIÁK
p páratlan prín. Vegyük észre, hogy (−1)k k ≡ k (mod p), k ha k páros, és (−1) k ≡ p − k (mod p), ha k páratlan. Ekkor az állítást a következ®képpen láthatjuk be. Futtassuk k -t 1-t®l (p − 1)/2-ig, és a megfelel® kongruenciák összeszorzásával kapjuk a következ® levezetést (mod p): p2 −1 p−1 p − 1 p−1 !(−1) 8 = (−1)1 1(−1)2 2 . . . (−1) 2 2 2 2 p −1 p−1 !(−1) 8 ≡ 2 · 4 · 6 · · · · · (p − 1) 2 p2 −1 p−1 p−1 p−1 8 2 !(−1) ≡ 2 ! 2 2 p2 −1 p−1 p−1 2 !(−1) 8 ! ≡ 2 p 2
Bizonyítás:
Mivel
( p−1 2 )!
Legyen
relatív prím
p-hez,
van inverze
(mod p),
amivel szorozva adódik,
hogy
p2 −1 2 ≡ (−1) 8 . p A kongruencia jobb és bal oldalán is csak
≡
±1 szerepelhet, tehát írhatunk = jelet
helyett. Ha
m
összetett, akkor is visszavezethetjük a problémát erre az esetre, az
??
tétel (4) állításának bizonyításánál látottakhoz hasonlóan, a következ® összefüggés segítségével:
(st)2 − 1 s2 − 1 t2 − 1 + ≡ 8 8 8 ahol
s, t
(mod 2),
páratlan számok.
3.14. tétel (Kvadratikus reciprocitás törvénye).
Legyen
m, n > 2
relatív
prím, páratlan számok. Ekkor
n m m
n
= (−1)
(m−1)(n−1) 4
.
A tétel bizonyítását jelen m¶ben nem közöljük, megtalálható a(z) [60] könyvben. A következ® algoritmus szolgáltatja az
n m
m>1
páratlan szám és
n≥0
egész bemenet esetén
Jacobi-szimbólum értékét. Felhasználjuk a
bi (x)
függvényt,
3.2. JACOBI-SZIMBÓLUM
33
2i -es tag együtthatóját adja vissza, továbbá a Csere(x, y) eljárást, amely x és y változó értékét cseréli meg. p változót az el®jelváltások paritásának tárolására használjuk, a ⊕ m¶velet jelentheti a bitenkénti összeadás, vagy a (mod 2) vett összeadás m¶veletét. tehát p értéke 0, vagy 1 lehet. amely az
x
nemnegatív egész bináris alakjában a
Jacobi(n, m) 1 2 3 4 5 6 7 8 9 10 11 12 13 14
p←0 n ← n (mod m) if n = 0
if
then return 0 b0 (n) = 1
then goto 10
p ← p ⊕ b1 (m) ⊕ b2 (m) n ← n/2
goto 5 if n = 1 then return 1 − 2p
p ← p ⊕ (b1 (n) ∧ b1 (m))
Csere(n, m)
goto 2
34
FEJEZET 3.
KVADRATIKUS KONGRUENCIÁK
4. fejezet
Testek Tegyük fel, hogy a
K
testben van olyan
α 6= 0
elem, amelyre alkalmas
n>0
egész számmal
nα = (α + · · · + α) = 0, ahol
α pontosan n-szer szerepel tagként. Legyen β tetsz®leges K -beli elem. Észnβ = 0 is fennáll, hiszen β = (β/α) · α, és innen
revehetjük, hogy ekkor
nβ = (β/α) · (α + · · · + α) = (β/α) · (nα) = 0. 0 6= α ∈ K n0 a legkisebb olyen pozitív egész, amelyre n0 α = 0 teljesül valamely 0 6= α ∈ K elemre. Ekkor nyilvánvaló, hogy n0 prímszám, hiszen ha feltennénk, hogy n0 összetett, akkor n0 = u · v írható, ahol n0 > u, v > 1, így n0 α = u · (v · α) = 0. Ekkor két eset lehetséges: vagy vα = 0, vagy vα = β 6= 0 és uβ = 0. Ez mindkét esetben ellentmond n0 minimális voltának, azaz n0 = p csak prímszám lehet. Ezt a p számot K karakterisztikájának nevezzük. Ez a p prímszám egyértelm¶en meghatározott. Tegyük fel ugyanis, hogy p 6= q prímekre fennáll, hogy pα = 0, illetve qα = 0. Ekkor az 1 = up+vq egyenlet alkalmas u, v egészekre megoldgató, Tehát beláttuk, hogy ha
ra teljesül, akkor ez
K
n ∈ N
esetén
nα = 0
legalább egy
bármely elemére fennáll. Legyen
mivel euklidészi gy¶r¶ben vagyunk, tehát kapjuk, hogy
α = 1 · αupα + vqα = 0. 35
36
FEJEZET 4.
TESTEK
0 6= β ∈ K és m ∈ N-re mβ = 0, akkor p | m. Valóban, ha p - m lenne igaz, akkor (p, m) = 1 miatt az 1 = up+mv egyenlet alkalmas u, v egészekre megoldgató, amint azt az el®bb láttuk. Ebb®l Könnyen belátható az is, hogy ha valamely
a következ® összefüggést kapjuk:
1 · upβ + vmβ = u(pβ) + v(mβ) = 0. Ez csak
β=0
0 6= β feltételünknek. nα = 0 valamely α 6= 0 testbeli
esetén teljesülhetne, amely ellentmond
+
n(6= 0) ∈ N , amelyre 0-karakterisztikájúnak (néha végtelen karaktenevezzük. Világos, hogy Q, R, C 0-karakterisztikájú.
Ha nem létezik olyan
elemre teljesülne, akkor a testet risztikájúnak) testnek
4.1. de níció.
F tetsz®leges test. K az F részteste, ha K ⊂ F és K F m¶veleteivel. Ekkor F test a K b®vítése, amelyet F : K F = 6 K , akkor valódi b®vítésr®l, illetve valódi résztestr®l
Legyen
maga is testet alkot val jelölünk. Ha beszélünk.
Fp (= GF (p)) a mod p vett maradékosztályok testét. Vegyük észre, K részteste Fp -nek, akkor tartalmaznia kell annak additív és multip-
Jelölje hogy ha
likatív egységelemét, továbbá a m¶veleti zártság miatt így az összes többit is. Tehát bármely
p prímszámra Fp nek nincs valódi részteste. Azt is könnyen megQ sem tartalmaz valódi résztestet.
állapíthatjuk, hogy
4.2. de níció. prímtestnek
Azon testeket, amelyek nem tartalmaznak valódi résztestet,
nevezzük.
Ha tekintjük egy tetsz®leges vesszük, akkor résztest
F -ben,
F -nek
egy
K
F
test összes résztestét és ezek metszetét
résztestét kapjuk. Világos, hogy
K
a legsz¶kebb
továbbá prímtest, hiszen nem tartalmazhat valódi résztestet.
K -t F prím résztestének
nevezzük.
A következ® tételben tulajdonképpen azt fogalmazzuk meg, hogy algebrai értelemben pontosan egy
0-karakterisztikájú prímtest van, míg a véges prímtestek
pontosan a prímszám modulusú maradékosztálygy¶r¶k.
4.3. tétel. kája
0,
és
Tetsz®leges
Fp -vel,
ha
F
F
test prím részteste izomorf
karakterisztikája a
p
Q-val,
prímszám.
ha
F
karakteriszti-
37
F p karakterisztikájú test prím részteste K . Mivel minden résztest, így K is tartalmazza F nullelemét (jelölje: 0) és egységelemét (jelölje: e), ezért az {1 · e, 2 · e, . . . , p · e = 0} elemeket is. Utóbbi halmaz testet alkot F m¶veleteivel, továbbá izomorf Zp -vel, tehát kaptuk, hogy algebrai értelemben
Bizonyítás: Legyen az
K = Zp . F 0-karakterisztikájú az e multiplikatív egységelemmel. Ekkor ke (k ∈ Z) alakú elemeket, továbbá l 6= 0 le (l ∈ Z) alakúakat, így a ke/le alakú elemeket is. A ke | k ∈ Z, l ∈ Z \ {0} le
Most legyen
F
minden részteste tartalmazza a
esetén az
alakú elemek testet alkotnak izomorf
F
m¶veleteivel, amely
F
legsz¶kebb részteste és
Q-val.
0-karakterisztikájú test, mint például R, C vagy a kvadratikus testek, Q b®vítése, illetve minden p prímkarakterisztikájú test Fp b®vítése. A következ® fogalmak fontosak az algebrában Összefoglalva mondhatjuk, hogy lényegében minden
és számelméletben is.
4.4. de níció. Algebrai számnak nevezzük azokat a komplex számokat, amelyek gyökei lehetnek egy racionális együtthatós nem azonosan nulla polinomnak, illetve
transzcendens számnak,
amelyek nem rendelkeznek ezzel a tulajdon-
sággal. Általánosítva:
4.5. de níció.
Legyen F tetsz®leges test, K az F részteste, továbbá α ∈ F . Azt α algebrai elem K felett, ha létezik olyan nem nulla K feletti amelynek α gyöke. Ha ilyen polinom nincs, akkor α transzcendens
mondjuk, hogy polinom,
elem K
felett.
A tévedések elkerülése végett, amikor tudni szeretnénk egy testbeli elemr®l, hogy transzcendens-e, vagy algebrai, fontos mindig kihangsúlyozni, milyen test elemér®l van szó és milyen résztest felett vizsgáljuk a kérdést. A jólismert egész számok fogalmának is megadjuk az általánosítását.
4.6. de níció.
Egy komplex számot
egész együtthatós f®polinomnak.
algebrai egésznek nevezünk, ha gyöke egy
38
FEJEZET 4.
Vegyük észre, hogy a racionális számtestben
√ Q( 5)
halmazát, de például a
Z
TESTEK
alkotja az algebrai egészek
kvadratikus testben az
√ 1+ 5 2 szám is egész, pontosabban algebrai egész, hiszen gyöke az
4.1.
x2 −x−1 polinomnak.
Testb®vítések
Ebben az alfejezetben a
testb®vítésekkel
kapcsolatos alapvet® gondolatokkal
fogunk foglalkozni.
4.7. de níció.
F részteste, és M ⊆ F . F -nek K -t és M -t is, K M halmazzal való b®vítésének nevezzük és K(M )-mel jelöljük. Ha M = {α} egy elem¶ halmaz, akkor egyszer¶ b®vítésr®l beszélünk, amelyet K(α) jelöl. Legyen
F
K
tetsz®leges test,
az
azt a legsz¶kebb résztestét, amely tartalmazza
4.8. de níció. eleme algebrai
F
Legyen
K
F részteste. F algebrai b®vítése K -nak.
tetsz®leges test és
felett, akkor
F
Könnyen belátható, hogy ha
F
más, mint egy
feletti vektortér.
tehát a skalár szorzás a egységelemet
1-gyel
V -beli
Ha
F
minden
V az F b®vítése, akkor V nem Valóban F elemei egyúttal V elemei is, test és
multiplikatív m¶velet, továbbá a multiplikatív
a∈F
a(v + w) = av + aw,
(2)
(a + b)v = av + bv ,
ahol
(3)
(ab)v = a(bv),
a, b ∈ F
(4)
1v = v ,
ahol
minden
4.9. de níció.
az
jelölve igazak a következ® összefüggések:
(1)
ziós akkor
K
F :K
ahol
v∈V
a, b ∈ F és
v, w ∈ V ,
és
és
v ∈V,
v ∈V,
esetén.
esetén, ha
végtelen b®vítésr®l,
F
mint
K
egyébként
feletti vektortér nem véges dimen-
véges b®vítésr®l
beszélünk.
4.1. TESTBVÍTÉSEK
39
Fontos fogalom a testb®vítések foka, amelyet a következ®képp de niáliunk:
4.10. de níció.
Az
dimenziója, amelyet
4.1.1.
F : K testb®vítés foka [F : K]-val jelölünk.
az
F
mint
K
feletti vektortér
Minimálpolinom
További fontos fogalmat vezetünk be, ehhez tekintsünk egy tetsz®leges Tudjuk, hogy
F [x],
az
F
F
testet.
feletti egyváltozós polinomok halmaza, f®ideálgy¶r¶t
alkot a polinom összeadással és szorzással, mint m¶velettel. Ez azt jelenti, hogy
F [x]
minden ideálja generálható egy elemmel. Legyen most
és tekintsünk egy
α∈F K
K
részteste
F -nek
felett algebrai elemet. Könnyen látható, hogy
Iα = {f (x) ∈ K[x] | f (α) = 0} , azaz azon
K
feletti polinomok halmaza, amelyeknek
α
gyöke, ideált alkot
F [x]-
ben.
4.11. tétel.
Legyen
K
Bizonyítás:
F testnek és α ∈ F K felett algebrai elem. g ∈ F [x] f®polinom létezik, amely generálja Iα -t.
részteste
Ekkor pontosan egy olyan
Az egzisztencia bizonyításához tegyük fel, hogy
h
minimális fok-
Iα -ban, b f®együtthatóval. Mivel F test, létezik b multiplikatív g = b−1 h f®polinom. Osszunk el maradékosan g -vel egy f ∈ Iα polinomot, ekkor
számú polinom
inverze. Ekkor tehát tetsz®leges
f = gq + r Mivel
Iα
ahol
r = 0,
vagy
r 6= 0
és
deg(r) < deg(g) = deg(h).
ideál, ezért igaz, hogy
r = f − gq ∈ Iα . h
fokszámának minimalitásából következik, hogy csak az
Tehát azt kaptuk, hogy tetsz®leges
Iα -beli
elem
g
r=0
eset állhat fenn.
többszöröse, azaz
Iα = hgi. Az unicitás bizonyításához tegyük fel, hogy létezik Ekkor viszont léteznie kell olyan
0
c, c ∈ F [x]
g 0 ∈ F [x], amelyre Iα = hg 0 i.
polinomoknak, amelyekre fennáll a
40
FEJEZET 4.
TESTEK
g = g 0 c0 és g 0 = gc. Ebb®l kapjuk, hogy g = gcc0 , vagyis cc0 az F egységeleme, 0 0 azaz c, c konstans polinomok. Mivel g és g is f®polinom, következik, hogy g = g0 .
4.12. de níció. F
algebrai elem
Legyen
K
n-edfokú,
szám
g
ha
K
tetsz®leges test és
F -nek. Ha α ∈ meghatározott g ∈ K[x]
egy részteste
felett, akkor azt az egyértlem¶en
az α elem K feletti minimálpolinomjának α K feletti fokszáma, speciálisan egy algebrai minimálpolinomja Q[x]-ben n-edfokú.
f®polinomot, amelyre nevezzük. Ekkor
F
Iα = hgi,
foka egyben
A következ® állítás a minimálpolinom tulajdonságait foglaljuk össze.
4.13. tétel. K fölött g elem
Legyen
F
felett, továbbá
K egy részteste F -nek, α ∈ F algebrai K feletti minimálpolinomja. Ekkor K fokszámú polinom, amelynek α gyöke.
tetsz®leges test és
g ∈ K[x]
az
α
elem
irreducibilis és a legalacsonyabb
Bizonyítás: Indirekt módon tegyük fel, hogy ható
h1 , h2 ∈ K[x]
g
nem irreducibilis, azaz felbont-
legalább els®fokú polinomok szorzatára.
g
fokszáma is na-
gyobb 0-nál, mivel van gyöke, tehát felírhatjuk, hogy
g = h1 h2 , Mivel
α
gyöke
g -nek,
ahol
1 ≤ deg(hi ) < deg(g) (i = 1, 2).
igaz, hogy
0 = g(α) = h1 (α)h2 (α). Ekkor viszont
h1 ,
amely ellentmond
vagy
g
h2
eleme
Iα -nak,
azaz
g
osztója
h1 -nek,
Most tegyük fel, hogy
α
gyöke egy tetsz®leges
f ∈ Iα teljesül, tehát g osztója f -nek. Mivel g deg(f ) > deg(g), így igazoltuk az állítást.
f ∈ K[x]
K
h2 -nek,
polinomnak. Ekkor
f®polinom, ezért
Az egyszer¶bb írásmód kedvéért érdemes bevezetni az elem
vagy
felbonthatóságának.
f = g,
mpK (α)
vagy
jelölést
α
test feletti minimálpolinomjára. Ide kívánkozik a következ® de níció,
amely tulajdonképpen egy komplex számoknál gyakran el®forduló fogalom általánosítása.
4.1. TESTBVÍTÉSEK
4.14. de níció. Ekkor
Legyen
α konjugáltjai
41
K
alatt
C-ben, továbbá α ∈ C algebrai elem K mpK (α) gyökeit értjük.
résztest
felett.
Mindig pontosan annyi konjugált van, ammennyi a megfelel® minimálpolinom foka, amint ezt a következ® állítás mutatja.
4.15. tétel. Ekkor
Legyen
mpK (α)-nak
K
résztest
C-ben,
továbbá
α ∈ C
algebrai elem
K
felett.
nincs többszörös gyöke.
Tegyük fel indirekt módon, hogy deg (mpK (α)) > 1 és c ∈ C nmpK (α)-nak, valamely n > 1 egészre. Tudjuk, hogy ekkor mpK (α) 0 algebrai deriváltjának (mpK (α)) c legalább n − 1-szeres gyöke. A minimálpolinom által generált ideál viszont minden polinomot tartalmaz, amelynek α gyöke,
Bizonyítás:
szeres gyöke
tehát
mp0K (α) ∈ hmpK (α)i, azaz
mpK (α) | mp0K (α), amib®l kapjuk, hogy
deg (mpK (α)) ≤ deg (mp0K (α)) , ami ellentmondás, tehát a bizonyítás kész.
4.1.2.
Algebrai testb®vítések
A következ® fejezetekben olyan testb®vítésekkel fogunk foglalkozni, amelyek nem tartalmaznak a b®vített test felett transzcendens elemeket. A vektorterekhez kapcsolódó alapvet® fogalmak ismeretében könnyen belátható a következ® állítás.
4.16. tétel.
Tetsz®leges
K
test minden véges b®vítése algebrai
K
felett.
: K] = n. Ez azt jelenti, hogy tetsz®leges β ∈ F elemre az n+1 darab 1, β , β , . . . , β n elem lineárisan nem független, mivel a vektorterünk n dimenziós. Tehát vannak olyan ai ∈ K együtthatók, amelyek nem mindegyike 0 és 0 ≤ i ≤ n, úgy hogy fennáll az Bizonyítás: Legyen [F 1 2
a0 + a1 β + a2 β 2 + . . . , an β n = 0
42
FEJEZET 4.
összefüggés. Ez pedig pontosan azt jelenti, hogy nemnulla polinomnak, azaz algebrai
K
β
gyöke egy
K
TESTEK
együtthatós
felett.
Egyszer¶ b®vítéseknél a b®vít®elem minimálpolinomjának a foka határozza meg a testb®vítés fokát. Nézzük például az el®bbi esetet, amikor fokszáma
n,
akkor
[K(α) : K] = n.
4.2.
Véges testek
α K
feletti
5. fejezet
Kvadratikus testek Az eddig bevezetett fogalmak felhasználásával a következ®képpen adhatjuk meg a dolgozatunk középpontjában lév® struktúrákat.
5.1. de níció.
Legyen
kvadratikus testnek
ϑ
egy másodfokú algebrai szám. Ekkor a
Q(ϑ)
testet
nevezzük.
Könnyen bizonyítható a következ® állítás:
5.2. tétel.
Minden kvadratikus test
√ √ Q( D) = {u + v D | u, v ∈ Q} alakú, ahol Az
1 6= D
négyzetmentes egész szám.
√ α=u+v D
szám konjugáltja
√ α = u − v D, normája
N (α) = αα = u2 − v 2 D. Világos, hogy
α, β ∈ Q
esetén
αβ = αβ ,
és így
N (αβ) = N (α)N (β). Az is könnyen észrevehet®, hogy a norma mindig egész szám, és lehet negatív is. 43
44
FEJEZET 5.
5.1.
KVADRATIKUS TESTEK
Algebrai egészek kvadratikus testekben
Minden témakör, amivel foglalkozunk ebben a dolgozatban kapcsolatban áll kvadratikus testek algebrai egészeivel. Ezért érdemes néhány sort szentelni ezen számhalmazok megismerésére.
√ D = −1 ( −1 = i) választással kapott Q(i) testet Gauss-féle számtestnek nevezzük. Q(i) (algebrai) egészei azok az α = u + vi alakú komplex számok, amelyek minimálpolinomja vagy els®fokú, és ekkor u ∈ Z, v = 0, vagy A
másodfokú, s az utóbbi esetben
(x − α)(x − α) = x2 − 2ux + u2 + v 2 egész együtthatós. Könnyen belátható, hogy
2u ∈ Z, és u2 +v 2 ∈ Z csak u, v ∈ Z
esetén teljesülhet. Tehát kapjuk, hogy a Gauss-féle számtest algebrai egészei a számelméletben jól ismert
Gauss-egészek
gy¶r¶je:
G = {a + bi | a, b ∈ Z} . Egyéb esetben a helyzet nem ilyen fel, hogy
√ α=u+v D
szép. Legyen algebrai egész, azaz az
D
tetsz®leges, és tegyük
(x − α)(x − α) = x2 − 2ux + (u2 − v 2 D) a = 2u, b = 2v , c = u2 −v 2 D. Tehát a, c ∈ Z, 4c = a − b D. Mivel b2 ∈ Z és D négyzetmentes, ezért b ∈ Z is
polinom egész együtthatós. Legyen és fennáll, hogy
2
2
teljesül. Tekintsük most azokat az eseteket, amikor D ≡ 2 (mod 4), vagy D ≡ 3 (mod 4). Mivel minden négyzetszám 4-gyel osztva 0, vagy 1 maradékot ad, ezért a és b csak páros szám lehet, és így u, v ∈ Z. Végül nézzük a D ≡ 1 (mod 4) esetet. Nyilván a ≡ b (mod 2), azaz 2(u − √ v) ≡ 0 (mod 2), tehát u − v ∈ Z. Ekkor a Q( D) egészeiben szerepl® u, v számok nem feltétlenül egészek. Eredményeinket összefoglalva kapjuk, hogy
√ Q( D)
a következ®:
D ≡ 2, 3 (mod 4)
esetén
√ ID = {m + n D | m, n ∈ Z},
egészeinek
ID
halmaza
5.2. KVADRATIKUS TESTEK EGYSÉGEI
D ≡ 1 (mod 4)
esetén
ID
5.2.
45
√ 1+ D = {m + nω | m, n ∈ Z}, ω = . 2
Kvadratikus testek egységei
Közismert tény a számelméletben, hogy minden algebrai számtest (így a kvadratikus testek is) algebrai egészei gy¶r¶t alkotnak. A zérusosztó-mentesség és kommutativitás teljesül, továbbá az 1 a multiplikatív egységelem. Tehát minden kvadratikus test algebrai egészei egységelemes integritási tartományt alkotnak. Természetes módon adódnak a kérdések, hogy mik az egységek, a prímek, a felbonthatatlanok az említett gy¶r¶kben, továbbá, hogy különböz®
ID -k milyen
algebrai struktúrát alkotnak. Ebben a fejezetben gyelmünket az egységekre fordítjuk, mivel a kés®bbiekben felhasználjuk ®ket, például a prímtesztelésnél. A többi kérdésre csak röviden válaszolunk.
5.3. de níció.
Egy kvadratikus test egységei, prím, illetve felbonthatatlan ele-
mei alatt algebrai egészeinek egységeit, prím, illetve felbonthatatlan elemeit értjük. Vizsgáljuk most az egységek UD halmazát tetsz®leges ID -ben. Világos, hogy 1, −1 ∈ UD . Továbbá α ∈ ID akkor és csak akkor egység, ha α | 1, amib®l αα = ±1 adódik szükséges és elégséges feltételként. 2 2 Ha D = −1, akkor az m + n = 1 egyenlet összes megoldásából az
U−1 = {1, −1, i, −i} halmazt kapjuk. A
D = −3
esetben az
(m + nω)(m + nω) = m2 + mn + n2 = ±1 egyenlet megoldásai
(±1, 0), (1, −1), (0, ±1), (−1, 1), U−3 = {±1, ±ω, ±ω}.
azaz
46
FEJEZET 5.
D 6= −1, −3, D < 0
Könny¶ belátni, hogy
KVADRATIKUS TESTEK
esetén
UD = {1, −1}. Tekintsük most a
D > 0 esetet. Ekkor végtelen sok egység van. Ehhez elég ζ egység, amelyre ζ 6= ±1 ugyanis ζ ∈ UD esetén ζ m
látni, hogy létezik olyan (m
= ±1, ±2, . . . )
is egység.
D >√ 0, és D ≡ 2 (mod 4), vagy D ≡ 3 (mod 4). Alkalmaztételét α-t D-vel helyettesítve: tetsz®leges Q-ra létezik p, q ∈ N
Tegyük fel, hogy zuk Dirichlet úgy, hogy
√ 1 q D − p < , 1 ≤ q ≤ Q, Q
amib®l kapjuk, hogy
√ √ √ 1 1 + 2q D ≤ 2Q D + , 0
√ 2 q D − p2 ≤ 2 D + 1 = C. Q2
√
Mivel egész
D irracionális, ennek az egyenl®tlenségnek végtelen sok megoldása (p, q) változókban. Van tehát olyan N ∈ Z, amelyre |N | ≤ C , és a
van
q 2 D − p2 = N egyenletnek végtelen sok különböz® gyöke van.
N 6= 0. Van tehát olyan (p1 , q1 ), (p2 , q2 ) √ megoldáspár, amelyre √ p1 ≡ p2 (mod N ), q1 ≡ q2 (mod N ). Legyen α1 = p1 − q1 D, α2 = p2 − q2 D, és ζ = α1 /α2 . Ekkor √ √ (p1 p2 − q1 q2 D) (p1 q2 − p2 q1 D) D α1 α2 = + = u + v D, ζ= α2 α2 N N Világos, hogy
és a feltételeink miatt
u, v ∈ Z.
Továbbá
N (ζ) = tehát
ζ
egység és
N (α1 ) = 1, N (α2 )
α1 6= α2 , α1 6= −α2 , tehát ζ 6= ±1. Ezért a ±ζ , ±1/ζ elemek 1-nél nagyobb. Tekintsük az 1-nél nagyobb
között, amelyek mind egységek, van
5.2. KVADRATIKUS TESTEK EGYSÉGEI
47
√ 1 < ζ = u + v D. Világos, hogy u, v > 0, mert ζ ∈ (−1, 1), √ ahol ζ = u + v D . Legyen ε a legkisebb 1-nél nagyobb egység, és κ > 1 egy l m tetsz®leges másik egység. Ha κ 6= ζ semmilyen l ∈ N-re, akkor ε < κ < εm+1 , m ezért (1 <)λ := κ/ε < ε is egység, ami lehetetlen. m Az összes 1-nél nagyobb egység tehát ε alakú (m = 1, 2, . . . ), és így egységeket. Legyen
UD = {±εm | m = 0, ±1, ±2, . . . }. A
D ≡ 1 (mod 4)
esetben
UD
(5.1)
struktúrája hasonló. Végtelen sok egység van,
amelyeket az
2 1 dy 2 x+ y − = ±1 2 4 egyenlet egész megoldásai szolgáltatnak. Megjegyezzük, hogy a
q 2 D − p2 = ±1 alakú egyenleteket a matematikában
Pell egyenleteknek
(5.2) nevezik tévedésb®l,
mivel Euler egy ilyen nev¶ angol matematikusnak tulajdonított egy algoritmust, amely
5.2 megoldásával kapcsolatos. Azt,
hogy végtelen sok megoldás van, Lag-
range bizonyította. A Pell egyenletek és különböz® általánosításaik fontos szerepet játszanak a számelméletben.
5.2.1.
Alapegység
A fenti gondolatmenet arra inspirál minket, hogy megkülönböztessünk egyet az egységek közül, amely el®állítja a többit hatványai segítségével, mint azt láttuk
5.1
képletben. Tekintsünk két példát, legyen
√ √ K1 = Q( 3), K2 = Q( 2). K1 -ben nincs olyan egység, amelynek normája −1, míg K2 normája 1 és −1 is lehet. A vizsgálatok azt bizonyítják, ha van
Észrevehetjük, hogy ben az egységek
−1
normájú egység egy valós kvadratikus testben, akkor egyértelm¶en létezik
olyan
σ > 1 −1
normájú egység, amelyre igaz, hogy minden egység el®áll
alakban valamely
m
egészre.
±σ m
Gondoskodni kell arról, hogy legyen a csupa 1 normájú egységet tartalmazó struktúrákban is hasonló elem. Ehhez tekintsük az alábbi de níciót és állításokat.
48
FEJEZET 5.
5.4. de níció.
Legyen
D>1
KVADRATIKUS TESTEK
négyzetmentes egész, továbbá
SD = {(x, y) | x, y ∈ N} ,
ha
D ≡ 2, 3
(mod 4),
és
n x y , | x, y ∈ N, x ≡ y 2 2
SD = Legyen
(a, b) ∈ SD
√ ε = a + b D.
±εm
ID -ben,
m
egészre. Belátható továbbá, hogy
amely nagyobb, mint 1, tehát
egyértelm¶. Az is bizonyított, hogy ha van
−1
amelyre igaz, hogy minden egység el®áll
−1
ε
létezése
σ > 1 −1
normájú egység,
alakban valamely
m
egészre.
√ Q( D)-ben van egység. Ekkor azt az egyértelm¶en létez® σ > 1 −1 normájú egysém igaz, hogy minden egység el®áll ±σ alakban valamely m egészre,
5.5. de níció. a
±σ m
ε
normájú egység egy valós kvad-
ratikus testben, akkor egyértelm¶en létezik olyan
get, amelyre
(mod 4).
pár mindig létezik, az 1 normájú egységek
alakban valamely
a legkisebb 1 normájú egység
normájú
D≡1
a2 −Db2 = 1 egyenletnek, amelyre a értéke Ekkor ε az 1 normájú alapegység ID -ben.
(a, b)
Bizonyítható, hogy a keresett
−1
ha
az a megoldása az
a legkisebb, továbbá
mindegyike el®áll
o (mod 2) ,
normájú
Legyen
D >1
alapegységnek
négyzetmentes egész úgy, hogy
nevezzük.
Megtartva a fenti jelöléseket, bizonyíthatjuk, hogy ha
√ Q( D)-ben
van
−1
nor-
májú egység, akkor
ε = σ2 , továbbá megadhatjuk a következ® de níciót:
5.6. de níció.
D > 1 négyzetmentes egész. σ , különben ε az alapegység.
Legyen
normájú egység, akkor
Ha
√ Q( D)-ben
van
−1
Megemlítünk még egy eredményt, amelyet Dirichlet bizonyított a XIX. században, továbbá kapcsolatos a mi kutatásainkkal is.
5.7. tétel. ID -ben
Legyen
p
olyan pozitív prím, amelyre
az alapegység normája
−1.
D ≡ 1 (mod 4)
fennáll. Ekkor
5.3. KVADRATIKUS FORMÁK ÉS ALAPDISZKRIMINÁNS
D
2 3 5 7 11 13
ε √ 3 + 2√ 2 2 +√ 3 (3 + √ 5)/2 8 + 3 √7 10 + 3√ 11 (11 + 3 13)/2
5.1. táblázat. Az alapegység
σ √ 1+ 2 − √ (1 + 5)/2 − − √ (3 + 13)/2
√ Q( D)-ben
49
norma
−1 1 −1 1 1 −1
az els® 6 prím esetén.
Ennek, és a többi alapegységre vonatkozó állításnak részletes bizonyítása megtalálható [1] könyvben, mint ahogy egy módszer is arra, hogy hogyan határozzuk meg az alapegységet egy valós kvadratikus testen. Jelen m¶ keretei között ezzel nem foglalkozunk, csak néhány példát adunk. Tehát tekintsünk néhány értéket. Az 5.1 táblázatban látható többek közt példa,
−1
√ Q( 5)
és
√ Q( 13)
D∈P esetén,
normájú alapegységre. Ahogy fentebb láttuk ebben az esetben nem minden
egész eleme
5.3.
√ Z + Z D-nek.
Kvadratikus formák és alapdiszkrimináns
Algebrai struktúrák egy jellemz® értéke a
diszkrimináns . A részletes de níciók
[1] könyvben megtalálhatók, jelen m¶ keretei között csak az Atkin féle elliptikus görbés prímteszt megértéséhez szükséges ismereteket közöljük.
5.8. tétel. Ekkor
K
Legyen
test
d(K)
√ K = Q( D)
kvadratikus test, ahol
D
négyzetmentes egész.
diszkriminánsa
d(K) =
4D, D,
ha ha
D≡ 6 1, D ≡ 1.
A prímtesztelés szempontjából fontos egy speciális polinom diszkriminánsának vizsgálata.
50
FEJEZET 5.
5.9. de níció. Kvadratikus formának
KVADRATIKUS TESTEK
nevezzük a következ® alakban adott,
egész számok feletti homogén kétváltozós polinomot:
ax2 + bxy + cy 2 .
5.10. de níció.
Egy
f (x, y) = ax2 + bxy + cy 2
kvadratikus forma
d(f )
diszkri-
minánsát a következ®képp de niáljuk:
d(f ) = b2 − 4ac. Vegyük észre, hogy bármely
d ≡ 0, 1 (mod 4)
alakú egész szám lehet egy kvad-
ratikus forma diszkriminánsa. Ezért szokás az ilyen alakú egészeket diszkriminánsnak nevezni. Közülük megkülönböztetett gyelmet kapnak azok, amelyek itt hasonló szerepet játszanak, mint a prímszámok az egészeknél.
5.11. de níció.
Egy
d
egész
alapdiszkrimináns,
ha nem osztható páratlan
prím négyzetével, továbbá
d≡1
(mod 4),
d ≡ 8, 12 Meg gyelhetjük, hogy minden
d
vagy
(mod 16).
diszkrimináns felírható
d = D · q2 alakban valamely san azok a
d
D
diszkriminánsra és
q
pozitív egészre. Látható, hogy ponto-
értékek lesznek alapdiszkriminánsok, amelyekre
q = 1.
Természetes módon adódik a kérdés, hogy mi a kapcsolat kvadratikus testek és alapdiszkriminánsok közt. A választ a következ® állítás adja.
5.12. tétel.
Tetsz®leges
d egész akkor és csak akkor alapdiszkrimináns, ha diszk-
riminánsa egy kvadratikus testnek. Mondhatjuk, hogy algebrai értelemben minden alapdiszkriminánshoz pontosan egy kvadratikus test tartozik. Bizonyos szerz®k a
d = 1
számot nem tekintik
alapdiszkriminánsnak, mások igen. Utóbbi esetben a racionális számtestet az
elfajult kvadratikus testnek
nevezik.
5.4. IDEÁLOSZTÁLYSZÁM
d(K) K
√ Q( −3)
d(K) K
√ Q( −15)
-3
51
-4
√ Q( −1)
-15
-19
√ Q( −19)
5.2. táblázat. Az els® néhány √ Q( D) kvadratikus testek.
-7
√ Q( −7) -20
√ Q( −5)
-8
√ Q( −2) -23
√ Q( −23)
-11
√ Q( −11) -24
√ Q( −6)
negatív alapdiszkrimináns és a megfelel®
K =
Felhívjuk a gyelmet, hogy nem tévesztend® össze az alapdiszkrimináns és a hozzá tartozó kvadratikus test b®vít®elemének négyzete, bár a kapcsolódó szakirodalmakban mindkett®t szokták
D-vel jelölni. Ez látható a(z) 5.2 táblázatban
is.
5.4.
Ideálosztályszám
Mondhatnánk viccesen, hogy ha találunk a matematikában egy olyan problémát, amellyel Gauss nem foglalkozott, akkor az nem is létezik. Ha behatóbban foglalkozunk a számelmélettel, akkor rájövünk, hogy ez nem is annyira merész kijelentés. Az úgynevezett
Gauss-féle osztályszám problémát
és a hozzá
kapcsolódó sejtéseit 1801-ben publikálta a névadó a Disquisitiones Arithmeticae cím¶ m¶ ([2]) 303 és 304-es cikkében. Egy
√ K = Q( D)
komplex kvadratikus test ideálosztályszámát
h(K)-val
je-
löljük, és a részletes de níciók el®tt megjegyezzük, hogy ez az érték dönti el, hogy mekkora eséllyel találunk
K
algebrai egészei segítségével megfelel® elliptikus gör-
bét az ECPP adott lépésében
(1/2h(K)).
Ahhoz, hogy a megfelel® görbéket ki
is számoljuk, meg kell határozni egy legfeljebb
h(K)
fokszámú polinom gyökeit.
Utóbbi két megállapításból láthatjuk, hogy prímtesztelés szempontjából azok a
jó kvadratikus testek, amelyek ideálosztályszáma kicsi.
5.13. de níció.
R egységelemes integritási tartomány, amelynek hányadosteste K , továbbá ∅ = 6 I ⊆ K . I törtideálja K -nak, ha teljesül a következ® három feltétel:
Legyen
52
FEJEZET 5.
KVADRATIKUS TESTEK
a, b ∈ I , akkor a + b ∈ I , ha a ∈ I, r ∈ R, akkor ar ∈ I , és létezik olyan 0 6= s ∈ R, amelyre sI ⊆ R.
(1) ha (2) (3)
5.14. példa. része 0, vagy
Tekintsük azon racionális számok
1/2: I=
nn 2
I
halmazát, amelyek tört
o |n∈Z .
Könnyen ellen®rizhet®, hogy az (1), (2) tulajdonság teljesül, továbbá
∅ = 6 2I = Z, azaz (3) is. Tehát I törtideálja Z-nek. A (3)-ban említett s értéket nevezhetjük tulajdonképpen az I -beli elemek közös nevez®jének, példánkban s = 2. K algebrai számtestet, és K algebrai egéIK gy¶r¶jét. Bizonyítható, hogy IK összes ideáljából és törtideáljából álló I(K) halmaz multiplikatív Abel csoportot alkot. Ha képezzük I(K) azon P (K) részhalmazát, amely IK f®ideáljaiból áll, akkor láthatjuk, hogy P (K) normálosztó I(K)-ban, tehát megkonstruálható a következ® faktorcsoport: Tekintsünk most egy tetsz®leges
szeinek
H(K) = I(K)/P (K).
5.15. de níció.
tar-
tozó
míg
A fenti jelölések megtartásával a K algebrai számtesthez H(K) = I(K)/P (K) faktorcsoportot K ideálosztály csoportjának, H(K)-nak a h(K) rendjét K ideálosztályszámának nevezzük. Fontos megjegyezni, hogy
H(K)
bizonyítottan mindig véges csoport ([1]).
A fenti fogalmak megismerésével már megérthetjük Gauss osztályszám prob-
n≥1 h(K) = n.
lémáját. A lényeg, hogy a nagy matematikus szerette volna megadni adott egészre azon komplex kvadratikus testek teljes listáját, amelyekre
n = 1, 2, 3
esetén úgy vélte összeállította a listákat, de ezek nem voltak telje-
sek. A hiányzó struktúrákat a XX. század második felében sikerült pótolni, a
3 < n ≤ 100 esetek pedig már a XXI. századra maradtak. A számelméletben jól Gauss-sejtés pedig az volt, hogy ha d alapdiszkrimináns tart −∞-hez, akkor h(d) −→ ∞. Ezt 1934-ben Heilbronn bizonyította. Könnyen bizonyítható egy K komplex kvadratikus test esetében, hogy az 1 ideálosztályszám, IK f®ideálgy¶r¶ és IK Gauss-gy¶r¶ ekvivalens állítások. ismert
5.4. IDEÁLOSZTÁLYSZÁM
d(K) K
-3
-4
√ Q( −3)
d(K) K
53
-7
√ Q( −1)
-19
-43
√ Q( −19)
-8
√ Q( −7)
√ Q( −43)
√ Q( −2) -67
-11
√ Q( −11) -163
√ Q( −67)
√ Q( −163)
5.3. táblázat. A 9 negatív alapdiszkrimináns és a megfelel®
√ K = Q( D),
ame-
lyek algebrai egészei f®ideálgy¶r¶t alkotnak. Az els® 5 ezek közül euklidészi kvadratikus test is egyben.
5.16. tétel. h(K) = 1 h(K) = 1
Bármely
K
algebrai számtest esetén
akkor és csak akkor, ha akkor és csak akkor, ha
IK IK
f®ideálgy¶r¶, és Gauss-gy¶r¶.
Térjünk vissza most arra a kérdésre, hogy mi a kapcsolata az osztályszámnak a prímteszteléssel. Már említettük, hogy az a jó alapdiszkrimináns, illetve a neki megfelel® kvadratikus test, amelynek alacsony az osztályszáma. Az ideális az lenne, ha minden komplex kvadratikus test algebrai egészei f®ideálgy¶r¶t alkotnának, azaz ideálosztályszámuk 1 lenne. A valóság sajnos sokkal prózaibb: pontosan 9 ilyen struktúra van, amelyek a(z) 5.3 táblázatban találhatók. Ezeket Heilbronn és Linfoot már ismerték 1934-ben, de nem tudták kizárni egy további létezését. Heegner 1952-ben szeretett volna publikálni egy bizonyítást, de nem fogadták el. Végül Baker (1966) és Stark (1967) egymástól függetlenül bizonyították az állítást. A teljesség kedvéért megjegyezzük, hogy a legkisebb 5 abszolút érték¶ alapdiszkriminánsra a megfelel® komplex kvadratikus test algebrai egészei euklidészi gy¶r¶t alkotnak. Valós esetben pontosan 16 euklidészi gy¶r¶ van, és sejtések szerint végtelen sok f®ideálgy¶r¶, ennek bizonyítása 2012 februárjában még nem ismert. Újra tekintsük a prímtesztelés problémáját, legyen Ekkor
√ Q( D)
α=a+b alakúak, ahol
−1 > D ≡ 1 (mod 4).
algebrai egészei
a, b ∈ Z.
√ D+ D 2 n racionális egészhez n. Azaz meg kell oldanunk a következ®
Feladat, hogy keressünk adott
olyan algebrai egészt, amelynek normája
54
FEJEZET 5.
egyenletet
a, b-re,
KVADRATIKUS TESTEK
amelynek jobb oldala egy kvadratikus forma:
n = αα = a2 + abD + b2
D2 − D . 4
Ezt a kérdéskört el®ször Lagrange vizsgálta [3] m¶vében, eredményeit Gauss tökéletesítette néhány évtizeddel kés®bb ([2]). Tekintsünk egy kicsit általánosabb formát:
n = f (x, y) = ax2 + bxy + cy 2 ,
(5.3)
2
f (x, y) determinánsa d(f (x, y)) = b −4ac. Legyen a 2x2 mátrixok speciális lineáris csoportja SL(Z, 2) a következ®képp de niálva: ahol
SL(Z, 2) = M ∈ SL(Z, 2)
A C
B D
| A, B, C, D ∈ Z
és
AD − BC = 1 .
lineáris operációról látható, hogy egy kvadratikus forma deter-
minánsát nem változtatja meg, s®t
f (x, y)
és az
M f (x, y) = g(x, y) = f (Ax + By, Cx + Dy) SL(Z, 2) csog(x, y)-ból f (x, y)
kvadratikus forma ugyanazokat az egészeket reprezentálják. Mivel port, minden elemének, azaz operációnak van inverze, tehát
visszakapható. Létrehozhatunk egy osztályozást kvadratikus formulák között. Legyen f1 , f2 kvadratikus formula ekvivalens, ha létezik olyan M ∈ SL(Z, 2), amelyre
M f 1 = f2 .
Jelben
f1 ∼ f2 .
5.17. de níció.
Egy
d = b2 − 4ac
formához tartozó
h(d)
osztályszám
Ha
d
alapdiszkrimináns, akkor
diszkriminánsú
∼
ax2 + bxy + cy 2
kvadratikus
osztályainak száma.
h(d)
megegyezik
h(K)-val,
ahol
K
a
d-hez
tartozó kvadratikus test. Visszatérve 5.3 megoldásának kérdésére, sajnos azt kell válaszolnunk, hogy csak akkor járunk sikerrel, ha a jobboldali kvadratikus forma a megfelel® osztályba esik. Továbbá az sem biztos, hogy gyököt vonni. Ennek esélye 5.3 egyenletet.
50%,
tehát végül
1/(2h(d))
d-b®l
tudunk
esélyünk van megoldani
6. fejezet
Prímszámok A prímszámokkal kapcsolatos kérdések több, mint kétezer éve foglalkoztatják az embereket. Még miel®tt rátérnénk ezek tárgyalására, a különböz® elnevezésekb®l adódó esetleges félreértések elkerülése végett, tekintsük a következ® két de níciót.
6.1. de níció.
R∗ \U (R) (1)
R
gy¶r¶ és
U (R)
az egységek halmaza. Ekkor a
p ∈
felbonthatatlan (irreducibilis),
a ∈ U (R) (2)
Legyen
elem
prím,
ha minden a, b ∈ R esetén p = ab-b®l b ∈ U (R) következik, minden a, b ∈ R esetén p | ab-b®l p | a vagy p | b következik.
vagy ha
Az olyan, két binér m¶velettel rendelkez® algebrai struktúrákat, amelyekben érvényes a
számelmélet alaptétele (Gauss-gy¶r¶k), a prímek és felbontha-
tatlanok halmaza egybeesik. Mivel az egész számok halmaza is Gauss-gy¶r¶ az összeadás és szorzás m¶veletével, bocsánatos b¶n, hogy általános és középiskolákban a felbonthatatlan elem de nícióját használják prímekre, mint ahogy azt mi is tesszük a fejezet hátralév® részében. Feltesszük továbbá, hogy ha másképp nem rendelkezünk, prímszám alatt, mindig egynél nagyobb egész számot értünk. Azt, hogy végtelen sok prímszám létezik, már Euklidész bizonyította, viszont a mai napig nem tudjuk, hogy az (p1 , p2 prímek ikerprímek, ha
ikerprímek
száma véges, vagy végtelen
| p1 − p2 |= 2). Nagyon valószín¶, hogy az x-nél cx/(ln2 x), alkalmas c pozitív kons-
kisebb ikerprímek száma aszimptotikusan 55
56
FEJEZET 6.
PRÍMSZÁMOK
tanssal. Brun 1919-ben megmutatta, hogy az ikerprímek reciprokösszege konvergens sort alkot. Ez a tény arra utal, hogy ha nincsenek is feltétlenül véges sokan az ikerprímek, de egyre ritkábban fordulnak el® a végtelen felé haladva. A szám, amihez az el®bb említett sor konvergál,
B = 1.9021605823 . . . ,
Brun-konstans. B értékének, minél pontosabb meghatározása prímrekordok problémakörébe tartozik. Ezen a területen kerülnek te-
az úgynevezett már a
rítékre olyan feladatok, mint például: keressünk minél nagyobb, bizonyos tulajdonságokkal rendelkez® prímeket, vagy ellen®rizzük egy sejtés helyességét számítógéppel a lehet® legnagyobb korlátig. Az egyik ilyen probléma
Goldbach-sejtés
páros
néven vált híressé. 1742-ben egy Eulernek írott levelében ve-
tette fel a gondolatot Goldbach, miszerint minden
n>5
egész szám felírható
három prím összegeként. Euler válaszában megírta, hogy ez a probléma ekvivalens azzal, hogy bármely háromnál nagyobb páros egész szám felírható-e két prím összegeként. A
páros megkülönböztetés azért ragadt a Goldbach-sejtésre, mert korábban a matematikus egy másik gondolata, amely szerint minden 5nél nagyobb páratlan szám el®áll három prím összegeként, kapta a
Goldbach-sejtés
páratlan
elnevezést. Megjegyezzük, hogy általában a páros eset vizs-
gálata van napirenden, mivel ebb®l rögtön következik a páratlan eset. Vinogradov 1937-ben bebizonyította a páratlan Goldbach-sejtést Sajnos nagy számon, a kés®bbi tökéletesítések ellenére is
10
nagy számokra. a több ezrediken
nagyságrendet kell értenünk. Az a tény, hogy számítógéppel a Goldbach-sejtés 2004-ben körülbelül mit
1017
nagyságrendig ellen®rzött, jól mutatja, hogy van még
lefaragni az elméleti korlátból.
A gyakran vizsgált kérdések közé tartozik még, hogy adott számig hány prím
hézag ) két szomszédos prím között.
fordul el®, mekkora a legnagyobb távolság (
Az ikerprímekhez hasonlóan, bizonyos szabályok szerint,
3-as, 4-es
stb. min-
ták is létrejöhetnek prímszámokból. Ezek el®fordulásainak megkeresése, illetve reciprokösszegük nagy pontosságú kiszámolása a számítógépes számelmélet témakörébe tartozó feladat.
faktorizáció prímteszt. El®bbi azt jelenti, hogy adott számot megpróbálunk felbontha-
Talán a két legfontosabb prímszámokkal kapcsolatos fogalom a és a
tatlanok szorzataként felírni. Meglep® lehet, hogy a két probléma megoldásának bonyolultsága mennyire eltér®. Míg prímteszt eredményesen végezhet® több ezer
6.1. PRÍMSZÁMOK ELOSZLÁSA
57
jegy¶ számokra is, addig a prímfaktorizációt legfeljebb pár száz jegy¶ számokra hajthatjuk végre, legalábbis ez a helyzet 2008-ban.
6.1.
Prímszámok eloszlása
A prímszámok eloszlását is már évezredek óta vizsgálják a matematikusok. A prímek
megjelenése azonban teljesen rendszertelen, így eddig elbuktak az olyan törekvések, mint például képletet adni prímszámok el®állítására, vagy kiszámolni, hogy egy adott intervallum hány prímet tartalmaz. Annak ellenére, hogy utóbbi probléma megoldására 2008 végén is pontosan egyetlen algoritmus létezik, nevezetesen állítsuk el® és számoljuk meg ®ket, az elmúlt b® kétszáz évben értek el a tudósok gyelemre méltó eredményeket a területen. Biztosan sokan forgattak már olyan matematikai szakkönyvet, amely számelméleti kérdésekkel foglalkozott. Gondolunk itt prímteszteléssel, illetve pozitív egészek prímtényez®s elóállításával kapccsolatos akgoritmusokra, de említhetnénk prímszámok eloszlásának vizsgálatát, valamint több kriptográ ában felmerül® problémát. Olvasás közben sokszor beleütközhettünk a következ® mon-
általánosított Riemann-sejtés igaz... . Az GRH , az angol megfel®jéb®l
datkezdésbe:
Tegyük fel, hogy az általánosított Riemann-sejtés szokásos rövidítése
(Generalized Riemann-hypothezis). Ha vesszük is a fáradtságot, hogy megnézzük, hogy tulajdonképpen mit is mond ki a GRH, nem biztos, hogy els® látásra megértjük azt, hogy mi köze van a prímteszteléshez, vagy a prímszámok eloszlásához. Ennek a fejezetnek a célja, hogy bizonyos eredmények közlése mellett megmutassa ezeket az összefüggéseket. A XVIII. század végén Gauss már sejtette, hogy hogyan lehet megbecsülni az
x
pozitív egésznél nem nagyobb prímek
számtétel
segítségével
π(x)
π(x)
számát. Az úgynevezett
6.2. tétel. lim
π(x)
x→∞
x ln(x)
= 1.
A prímszámtétel segítségével aszimptotikusan becsülhetjük az szám értékét is. Jelölje
pn
az
prím-
értékét becsülhetjük.
n-edik lim
x→∞
prímszámot, ekkor
pn = 1. n ln(x)
n-edik
prím-
58
FEJEZET 6.
PRÍMSZÁMOK
πZ (x, k, l)-lel jelöljük azoknak a p ≤ x egészeknek a számát, amelyekre p ≡ l (mod k) teljesül, igaz a következ® állítás is, amelyet Dirichlet bizonyított Ha
a Dirichlet karakterek, illetve az L-függvények segítségével.
lim π(x, k, l) = ∞,
x→∞ ha
(k, l) = 1. π(x, k, l)-lel jelöljük azoknak a p ≤ x p ≡ l (mod k) teljesül. Ekkor a prímszámtétel
A Dirichlet-tétel általánosítható, ha prímeknek a számát, amelyekre értelmében
lim
πZ (x, k, l) x ln(x)
x→∞ Nyilvánvaló, hogy hogy
(k, l) > 1
=
1 . ϕ(k)
esetén legfeljebb véges sok
p
prímre teljesülhet,
p ≡ l (mod k).
Csebisev volt az els®, aki lényegesen többet mondott
π(x)-r®l,
nevezetesen
bebizonyította, hogy
0, 92 < ha
x > x0 ,
ahol
x0
π(x)
< 1, 105,
x ln(x)
alkalmas állandó.
Végül a prímszámtételt egymástól függetlenül Hadamard és de la Vallée Poussin bizonyította 1896-ban. Szokásos a prímszámtételt a
x ln(x)
π(x) ∼ alakban is felírni.
Az elmúlt több mint 200 évben sokan próbálkoztak
π(x)
minél pontosabb
közelítését adó formulát adni. Gauss a XVIII. század végén már használta a
x
Z Li(x) = 2 formulát
π(x)
du ln(x)
közelítésére, tehát szokásos formában írva a prímszámtétel:
Z π(x) ∼ 2 Ismeretes, hogy alkalmas
C
és
A,
x
du . ln(x)
illetve
Ck
és
Ak
állandókkal
6.1. PRÍMSZÁMOK ELOSZLÁSA
59
√ |π(x) − Li(x)| ≤ C · x · e−A ln(x) ,
(6.1)
illetve
√ π(x, k, l) − Li(x) ≤ Ck · x · e−Ak ln(x) . ϕ(x)
(6.2)
Noha Riemann-nak nem sikerült bizonyítani a prímszámtételt, de adott egy formulát, amely
jobban közelíti
R(x) =
π(x) értékét, mint a fent említett képletek. Az ∞ X µ(n) · Li(x1/n ) n n=1
µ(x) a Möbius függvényt jelenti, Riemann függvény néven vált ismertté. Egzakt számolások azt támasztják alá, hogy R(x) pontosabb, mint Li(x), vagy x/ ln(x). Ezt tanulmányozhatjuk a következ® táblázatban:
kifejezés, ahol
x 8
10 109 ... 1015
π(x)
x/ ln(x)
Li(x) − π(x)
R(x) − π(x)
5.761.455 50.847.534 ... 29.844.570.422.669
−332.774 −2.592.592 ... −891.604.962.453
754 1.701 ... 1.052.619
97 −79 ... 73.218
A kiszámolt értékek azt sugallják, hogy minden
x-re Li(x) > π(x)
fennáll.
Valójában err®l Gauss és Riemann is meg voltak gy®z®dve, azonban Litlewood 1914-ben belátta, hogy
x2 < . . .
Li(x) > π(x) végtelen sokszor el®jelet vált az x0 < x1 <
számoknál.
A Riemann-hipotézis feltételezésével Skewes megmutatta 1933-ban, hogy 1034
x0 < 1010
.
Ez a korlát volt sokáig a matematikában természetes módon felbukkanó legnagyobb szám. Manapság ez a korlát már a Riemann-hipotézis feltevése nélkül is lejjebb faragható.
60
FEJEZET 6.
6.2.
PRÍMSZÁMOK
Riemann sejtései
A matematikusok mindig is törekedtek arra, hogy a ben el®forduló
p
ln(x)
(6.1), illetve (6.2) képletek-
értéket tovább nomítsák. A prímszámok eloszlásának
elméletében alapvet® jelent®ség¶ az úgynevezett
Riemann-féle ζ függvény ,
amelynek vizsgálatát igazság szerint már Euler kezdeményezte:
∞ X 1 ζ(s) = . s n n=1 Könny¶ belátni, hogy valós
s-re, s > 1
(6.3)
esetén
(6.3)
konvergens, valamint megegyezik a
Y p végtelen sorozattal, ahol
p
jobb oldala abszolút
1 1 − p1s
végigfut a prímszámok halmazán. A
∞ X Y 1 1 , (s > 1) = s n 1 − p1s p n=1
ζ(s) =
(6.4)
reláció tulajdonképpen az egyértelm¶ prímfelbontás analitikai megfelel®je. Euler érvelése szerint, ha véges prím lenne, akkor akkor a jobb oldal határértéke
1
s→
esetén véges lenne. A baloldal határértéke azonban nyilván végtelen, tehát
végtelen sok prímszám van. Természetesen
(6.4)-b®l
több is levezethet®. Tekintsük a következ® számo-
lást:
ln(ζ(s)) =
X p
=
XX ∞ 1 1 −m·s − ln 1 − s = p = p m p m=2
X 1 X 1 X 1 + . s p m p pms p m≥2
Az utolsó összeg
s≥1
esetén kisebb, mint
∞ XX p m=2
p−m =
X p
1 , p(p − 1)
6.2. RIEMANN SEJTÉSEI
ezért
ha
61
X 1 → ∞, ps p
s → 1. Dirichlet, Euler gondolatmenetét folytatandó, bevezette az
L(s, χ) := függvényeket, ahol
χ(n)
richlet L-soroknak féle azonosság :
Y
1 1−
χ(p) ps
,
(6.6)
Dirichlet egyik célja volt a következ® állítás bizonyítása:
X p≡l
(6.7)
Mivel
DiEuler-
Dirichlet karakter. Szokás ezeket a függvényeket
p
(s > 1).
(6.5)
is nevezni. Könnyen levezethet® az úgynevezett
L(s, χ) = ahol
∞ X χ(n) ns n=1
(mod k)
1 → ∞, (s → 1). ps
(6.7)
jobb oldalán
χ(p) 1 ps < 2 , ha
s > 1,
továbbá a sorozat abszolút konvergens, ezért
Vegyük most
(6.6)
L(s, χ) 6= 0,
ha
mindkét oldalának logaritmusát:
ln (L(s, χ)) =
X X χ(pm ) 1 · ms . m p p m≥1
Ebb®l kapjuk, hogy
X 1 1 X 1 X χ(l)χ(pm ) χ(l) ln(L(s, χ)) = · = ϕ(k) χ mpms ϕ(k) χ pms p,m
s > 1.
62
FEJEZET 6.
=
∞ X 1 m m=1
1
X pm ≡l
(mod k)
pms
X
= p≡l
(mod k)
X 1 1 + s p m m≥2
PRÍMSZÁMOK
1
X pm ≡l
(mod k)
pms
=
= u(s) + v(s). Nyyilvánvaló, hogy
0 ≤ v(s) ≤
X p
Ha
χ = χ0
1 ≤ 1. p(p − 1)
f®karakter, akkor
Y 1 L(s, χ0 ) = 1 − s ζ(s) p p|k
miatt
L(s, χ0 ) → ∞, s → 1 + 0. Nem nehéz belátni, hogy (6.5) jobb oldala konvergens s > 0 χ 6= χ0 . Dirichlet bebizonyította, hogy L(1, χ) 6= 0, ha χ 6= χ0 , amib®l levezette a (6.7) állítást. Itt kell megjegyeznünk, hogy a ζ(s) függvény értékének kiszámolása még egész s értékek esetén is megoldhatatlan problémát jelent a matematikusokha
esetén, ha
nak. Például tetsz®leges páratlan szám esetén azt sem tudjuk, hogy racionális megoldást kapunk, avagy sem. 2002-ben nagy eredménynek számított, annak bizonyítása, hogy
ζ(5), . . . , ζ(21)
közül az egyik racionális. Páros számok ese-
tén, ha nem is sokkal, de jobb a helyzet, hiszen tudjuk például, hogy illetve
ζ(4) =
π4 90 . Az el®bbi, pontosan
ζ(2) = kiszámolása a
ζ(2) =
bázeli probléma
π2 6 ,
∞ X 1 n2 n=1
néven vonult be a matematika történelmébe,
és megoldása nagy sikert hozott Eulernek. 1860-ban Riemann megmutatta, hogy a prímszámok eloszlását a vénynek, mint komplex
s
ζ(s)
függ-
változós függvénynek a mélyebb tanulmányozásával
lehet megismerni. Riemann két f® eredménye a következ®:
6.2. RIEMANN SEJTÉSEI
(1)
ζ(s)
A
függvény
63
analitikusan
s = 1
meromorf, egyetlen pólusa van az residuuma
1.
az
Azaz
ζ(s) −
egész
komplex
síkra
folytatható,
pontban, amely els®rend¶ pólus, és
1 s−1
egész érték¶ függvény.
ζ(s)
(2)
kielégíti az alábbi függvényegyenletet:
π ahol
Γ
−s 2
Γ
s 2
ζ(s) = π
−s 2 (1−s)
Γ
1 (1 − s) ζ(1 − s), 2
az Euler-féle gamma függvény.
Re(s) > 1 félsíkon ζ(s) 6= 0, a fenti függvényegyenletb®l követke s zik, hogy a Re(s) < 0 félsíkon a ζ(s) függvénynek ott van gyöke, ahol a Γ 2 függvénynek pólusa van, tehát az s = −2, −4, −6, . . . pontokban. Ezeket a ζ(s) függvény triviális gyökeinek , a 0 ≤ Re(s) ≤ 1 sávot kritikus sávnak neMivel a
vezzük. Riemann a következ® sejtéseket fogalmazta meg:
(i) akkor
(ii)
ζ(s)-nek a kritikus 1 − ρ és ρ is gyök. Jelölje
N (T )
a
sávban végtelen sok gyöke van. Ha
ζ(s)
függvény
ρ
egy gyök,
|Im(s)| ≤ T , 0 ≤ Re(s) ≤ 1
tégla-
lapba es® gyökeinek a számát. Ekkor
T N (T ) = ln 2π (iii)
T 2π
T + |ln(T )| . 2π
(6.8)
A
ζ(s) =
s −1 1 s(1 − s)π 2 s Γ ζ(s) 2 2
függvény, a függvényegyenlet miatt az
1 − s,
−
(6.9)
s − 1/2 páros függvénye, ezért ζ(s) = ζ =
továbbá
ζ(s) = e
As+B
Y ρ
s 1− ρ
s
eρ ,
(6.10)
64
FEJEZET 6.
ahol
A, B
(iv)
állandók,
PRÍMSZÁMOK
ρ pedig a ζ(s) függvény kritikus sávba es® gyökein fut végig.
Legyen
Λ(n) =
n = pl , különben .
ln(p), 0,
ha
Ψ(x) =
ahol
X
p
prím, és
(l = 1, 2, . . . ),
Λ(n).
(6.11)
n≤x Ekkor
Ψ(x) − x = −
ρ (v)
Riemann sejtés ,
A
híres bizonyított, a következ®:
6.3. sejtés.
ζ 0 (0) 1 1 − − ln 1 − 2 . ρ ζ(0) 2 x
X xρ
A
ζ(s)
(6.12)
amely a mai napig (2008. novembere) nem
függvény kritikus sávba es® gyökei valamennyien a
Re(s) =
1 2
egyenesre esnek. A (ii) és (iv) sejtést Mangoldt bizonyította 1895-ben, illetve 1905-ben, a (iii) sejtést Hadamard 1893-ban. 1914-ben Hardy belátta, hogy végtelen sok gyök, A. Selberg 1942-ben pedig, hogy a gyökök pozitív százaléka erre az egyenesre esik. Van Koch bizonyította 1901-ben, hogy a Riemann sejtés ekvivalens a következ® formulával:
1 π(x) = Li(x) + O x 2 · ln(x) . Ψ(x) − x és π(x) − Li(x) nagyságrendje között szoros összefüggés van. π(x) ∼ Li(x) akkor és csak akkor teljesül, ha Ψ(x) ∼ x. (6.11) felhasználásával nem nehéz belátni, hogy utóbbi ekvivalens azzal, hogy ζ(s) 6= 0, ha Re(s) = 1. A
Tulajdonképpen Hadamardnak és de la Vallée-Poussin-nek ezt sikerült bizonyítaniuk. A ζ(s) függvény gyökmentes tartománya és a maradéktagja között szoros összefüggés van. Legyen s = σ + it. Ha
π(x) − Li(x) = O xα+
6.2. RIEMANN SEJTÉSEI
65
> 0 állandóval teljesül, valamely rögzített α < 1 esetén, akkor a σ > α félsíkon a ζ(s) függvénynek nincs gyöke. Megjegyezzük, hogy az O -ban fellép® állandó függhet -tól, továbbá, hogy az állítás megfordítása is igaz. minden
1958-ban trigonometrikus összegek I. M. Vinogradovtól származó becslésével, és számos más új gondolattal, Vinogradov és Korobov egymástól függetlenül bizonyította, hogy
ζ(σ + it) 6= 0, σ ≥1−
alkalmas
c>0
ha
c 2/3
ln
(|t| + 10)
· ln (ln(|t| + 10))
numerikus állandóval. Innen következik, hogy
3/5 −3/5 , Ψ(x) = x + O x · e−c1 ·x1 ·x2 ha
x≥0
és
3/5 −3/5 , π(x) = Li(x) + O x · e−c1 ·x1 ·x2
x ≥ 0, és c1 > 0 megfelel® numerikus ln(ln(x)). Adott k és l, (k, l) = 1 esetén legyen
ha
x1 = ln(x), x2 = ln(x1 ) =
állandó,
X
π(x, k, l) =
p≤x,p≡l
X
Ψ(x, k, l) =
n≤x,n≡l
1,
(mod k)
Λ(n),
(mod k)
és
Ψ(x, χ) =
X
Λ(n)χ(n).
n≤x A prímszámtétel számtani sorozatokra történ® általánosítása a π(x, k, l) ∼ Li(x) ϕ(k) formula. Ez ekvivalens azzal, hogy L(s, χ) 6= 0 a Re(s) = 1 egyenesen minden χ (mod k) Dirichlet karakterre. Az alábbi állítást szokás úgy említeni, mint az
sejtés .
6.4. sejtés.
Minden
χ
karakterre az
L(s, χ)
valamennyi gyöke a
Re(s) = egyenesre esik.
1 2
általánosíatott Riemann
függvény
0 ≤ Re(s) ≤ 1
sávba es®
66
FEJEZET 6.
PRÍMSZÁMOK
7. fejezet
Szita algoritmusok
Sokszor merül fel az igény arra, hogy nagy számú prímet kell el®állítanunk, például a Goldbach-sejtés ellen®rzésénél, vagy prímek közti hézagok vizsgálatánál. Erre a mai napig is talán a legalkalmasabb módszer egy többezer éve ismert eljárás, amely
N
eratosztenészi szita
néven vált ismertté. Az algoritmus valamely
bemen® értékre megadja 3-tól kezdve az
N -nél
nem nagyobb prímszámokat.
Az eredmény a Tábla[j] vektorban képz®dik úgy, hogy ha a
2j + 3
prímszám. 67
j -edik elem 1, akkor
68
FEJEZET 7.
Eratosztenész(N ) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
n ← b(N − 1)/2c j←0 for i ← 1 to n do Tábla[i] ← 1 while Tábla[j] = 0 j ←j+1 i ← 2j 2 + 6j + 3 if i ≥ n
then return Tábla
←0 i ← i + 2j + 3 if i ≥ n then j ← j + 1 Tábla[i]
goto 5 else goto 10
SZITA ALGORITMUSOK
8. fejezet
Prímtesztek n ∈ N szám összetett, akkor felírható n = ab alakban, ahol a, b ∈ N, a > 1, b > 1, és így
Ha valamely továbbá
min(a, b) ≤ Annak eldöntését, hogy
√
n.
n prím vagy összetett, elvégezhetjük a következ® módon,
egy korai algoritmus segítségével:
Els®-prímteszt(n) 1 2 3 4
√
for d ← 2 to b nc do if d | n then return összetett return prím Látható, hogy ez az algoritmus a gyakorlati életben nagy számokra használ-
hatatlan, annak ellenére, hogy elméletileg faktorizálásra is használható, hiszen ha
n
összetett a
d
változóban el®áll az els® prímfaktor. Mivel a prímtesztel®
algoritmusoknak külön fejezetet szentelünk, ezért itt csak azok megértéséhez szükséges alapfogalmakat és állításokat ismertetünk. Ilyen például egy jól ismert elméleti kritérium, a
Wilson-féle kongruencia tétel , mely szerint: 69
70
FEJEZET 8.
8.1. tétel.
PRÍMTESZTEK
Az
(n − 1)! + 1 ≡ 0
(mod n) n
kongruencia akkor és csak akkor teljesül, ha
prímszám.
n ∈ N összetett. Ekkor van van olyan d ∈ N 1 < d < n, és így d | (n − 1)!. Tehát d - (n − 1)! + 1 fennáll, következésképpen n - (n − 1)! + 1, azaz kaptuk, hogy
Bizonyítás: El®ször tegyük fel, hogy osztója, amelyre
(n − 1)! + 1 6≡ 0 Most legyen
n
prímszám. Ha
n = 2,
(mod n) .
akkor
(2 − 1)! + 1 ≡ 0
(mod n)
fennáll, tehát feltehetjük a továbbiakban, hogy
ax ≡ 1
n > 2.
(mod n)
kongruenciának pontosan egy megoldása van, ha miatt teljesül minden
(mod n).
1 ≤ a ≤ n−1
(a, n) = 1.
Ez
n
prím volta
esetén. Jelölje az egyetlen megoldást
a−1
Vegyük észre, hogy
a ≡ a−1 csak az
Tudjuk, hogy az
a ≡ 1 (mod n)
és
(mod n)
a ≡ n − 1 (mod n) n−1 Y
a≡
a=1
n−1 Y
a−1
esetben fordulhat el®. Mivel
(mod n)
a=1
fennáll, és a bal, illetve jobb oldalon lév® tényez®kkel, kivéve
a=1
és
a = n−1
értékeket, egyszer¶síthetünk. Tehát kapjuk, hogy
(n − 1)! ≡ n − 1 ≡ −1
(mod n) ,
amivel az állítást bizonyítottuk. A prímtesztelést
ipari méretekben manapság a nyilvános kulcsú kriptog ra kus rendszereknél használják. Itt a nyilvános kulcs két nagy prímszám szorzatából áll. A nagy persze relatív fogalom. Noha isnerünk olyan prímet,
71
amely bizonyítottan 9 millió számjegynél is több®l áll, a gyakorlati életben általában elég pár száz számjegy¶ prímekkel dolgozni. Egyrészt a kódfeltöréshez a nyilvános kulcs faktorizációja szükséges, amely már ennyi 2-300 szájegy esetén is lehetetlennek t¶nik, másrészt túl nagy prímek használatával a kódolás
költsége is megn®.
A prímteszteléss kapcsolatos kutatások során már régen megkülönböztethet® must
tek
két
irány.
adjon
a
Mindkett®ben
prímtulajdonság
a
törekvés
eldöntésére.
az, A
hogy
gyorsabb
algorit-
valószín¶ségi prímtesz-
prímteszt!valószín¶ségi biztosan megmondják adott n pozitív egészr®l, hogyha az összetett szám, azonban a másik válasz amit adni tudnak nem az,
n prím, hanem hogy n valószín¶leg prím. Vannak módszerek arra, hogy a tévedés valószín¶sége gyakorlati szempontból elhanyagolható érték alá s¶llyedhogy
jen. Az
egzakt prímteszteknek
esetében az elvárt válaszok, hogy
n prím, vagy
n összetett. Az ilyen tesztelést hívják angolul gyarul talán
primality proving-nak, amely ma a prímtulajdonság bizonyításának fordítható. Használatos még a
determinisztikus , kifejezés az egzakt helyett, illetve a nemdeterminisztikus a valószín¶ségi helyett.
Összefoglalva, a valószín¶ségi prímtesztek használata esetén lemondunk arról, hogy száz százalékos biztonsággal állíthassuk, hogy egy
n pozitív egész prím,
viszont implementációjuk jóval gyorsabban fut, mint a determinisztikus teszteké, tehát a gyakorlati életben jobban használhatók. Az egzakt teszteknek inkább az elméletben van jelent®ségük. Kiemelhetjük itt az
AKS-algoritmust
amelynek
annak ellenére, hogy az eljárás gyakorlati megvalósítása még sok problémát vet fel a számítógép programozóknak, gondolunk itt például a nagy tárigényre, bizonyos számelméleti sejtések azt sugallják, valószín¶leg nem pusztán elméleti jelent®séggel bír. Agrawal, Kayal és Saxena 2002-ben publikálták ezt a determi-
?
nisztikus algoritmust [ ]-ben, amely nagy áttörésnek számít a prímtesztek történetében. Mondhatjuk ezt azért, mert a szerz®k bizonyítják, hogy a prímszámok halmaza a
P
nyelvosztályba tartozik. Ez azt jelenti, hogy egy
n
pozitív egész
szám prím mivoltának eldöntése megoldható annyi id® alatt, amely polinomiális függvénye.
dlg ne-nek
72
FEJEZET 8.
8.1. A
Valószín¶ségi prímtesztek, pszeudoprímek
SolovayStrassen-teszt
néven ismert eljárásnál az Euler-kritérium vizsgá-
latára épül. Az algoritmus ismertetésénél felhasználjuk a letve feltesszük, hogy a az
PRÍMTESZTEK
[x, y]
Random(x, y)
Jacobi
eljárást, il-
függvény egy véletlen számot szolgáltat
intervallumból.
SolovayStrassen-prímteszt(n) 1 2
d ← Random(1, n) a(n−1)/2 6≡ Jacobi(a, n) (mod n)
if
then return összetett else return valószín¶leg prím
3 4
Az eljárás érdekessége, hogy valójában valószín¶ségi teszt, de a szerz®k megmutatták, hogy csak véges sok összetett szám esetén érték esetén legfeljebb
(n − 1)/2
téved, azaz összetett szám elégíti ki a
a(n−1)/2 ≡
a n
n
bemeneti
(mod n)
kongruenciát. Ez azt jelenti, hogy az algoritmus megfelel® számú ismétléssel és megfelel®en választott
a
értékekkel tetsz®legesen megbízhatóvá tehet®. Termé-
szetesen a determinisztikusság eléréséhez, azaz a nulla hibaszázalékhoz, annyi ismétlésre van szükség, ami gyakorlatilag használhatatlanná lassítja az algoritmust. A MillerRabin-teszt,
manapság talán a leggyakakrabban használt va-
lószín¶ségi prímteszt. Bizonyítható, hogy az imént ismertetett módszernél biztonságosabb, azaz nem téved, ha a téved. Legyen
n > 8
SolovayStrassen-prímteszt
nem
páratlan egész, amelyr®l szeretnénk eldönteni, hogy prím-e.
Az alapötlet a következ®: írjuk fel
n-et
az
n = 1 + 2k q alakban, ahol ha
n
q
páratlan. Legyen továbbá
1
prím, akkor az Euler-Fermat tétel értelmében
an−1 ≡ 1
(mod n),
tetsz®leges egész. Ekkor,
8.1. VALÓSZÍNSÉGI PRÍMTESZTEK, PSZEUDOPRÍMEK
73
amib®l kapjuk, hogy
k
a2
q
≡1
(mod n).
Tekintsük a következ® sorozatot:
aq
(mod n), a2q
(mod n), a4q
Láttuk tehát, hogy az
(8.1)
(mod n), . . . , a2
sorozat utolsó eleme
prím, akkor az utolsó el®tti elem csak
1,
x2 ≡ 1
vagy
−1
1.
k
q
(mod n).
(8.1)
Vegyük észre, hogy ha
n
lehet, mivel
(mod n)
esetén
x2 − 1 ≡ 0
(mod n),
amib®l
n | (x + 1)(x − 1)
következik, tehát megjelenik az
1,
sorozatoknak
x = 1, vagy x = −1 áll fenn. Azokat a sorozatokat, amelyekben −1 van, jó
és ha ez nem az els® elem, akkor közvetlenül el®tte
nevezzük.
Természetesen, ha
n prím, akkor mindig jó sorozatot kapunk. Ha n összetett,
akkor lehet, hogy jó sorozatot kapunk, lehet, hogy nem. A fenti tulajdonsággal rendelkez®
a számot tanúnak nevezzük, ha összetett n esetén nem jó sorozatot a cinkos , ha összetett n esetén is jó sorozatot szolgáltat.
kapunk, míg
74
FEJEZET 8.
PRÍMTESZTEK
MillerRabin(n) 1 2 3 4 5 6 7 8 9 10 11 12 13
a ← Random(1, n) k ← log2 (n − 1)/2 j←k b ← aq (mod n) if (((j = k) and (b = 1))
or (b = n − 1)) then return valószín¶leg prím if ((j < k) and (b = 1)) then return összetett j ←j−1 j>0 then b ← b2 (mod n)
if
goto 5 return összetett
Világos, hogy a módszer hatékonysága többek közt azon is múlik, hogy hány tanú van
1
és
n
közt. A következ® eredmény
Miller-tétel
néven vált ismertté,
és azt sugallja, hogy viszonylag könnyen találhatunk tanút.
8.2. tétel.
Ha az általánosított Riemann-sejtés igaz, és
n >8
összetett, nem
prímhatvány egész, akkor van olyan
a < 2(ln(n))2 alapszám, amellyel a Miller-Rabin-prímteszt felfedezi, hogy
n
összetett.
A Miller-Rabin-teszt hatékonyságát mutatja az a gyakorlati észrevétel, hogy pusztán az
a = 2, 3, 5
szám van, amely
alapszámmal számolva
25 · 109 -ig
csak
13
olyan összetett
becsapja.
Az ebben az alfejezetben tárgyaltak fogalmak prímtesztelésekben való fel-
használására a következ® fejezetekbenben láthatunk további példákat.
9. fejezet
Prímrekordok 2005-ben Járai Antal professzor vezetésével számítógépes számelméleti kutatások kezd®dtek tanszékünkön. Ennek egyik részterülete a prímszámokhoz kapcsolható. Itt a klasszikus kérdések vizsgálata mellett (faktorizáció, prímteszt, szita módszerek), úgynevezett rövid magyarázatra szorul.
prímrekordok elérése volt a célunk. A fogalom
Azt már Euklidész bizonyította, hogy végtelen sok prímszám létezik, viszont azt, hogy végtelen sok ikerprím van, még senkinek nem sikerült belátni. Egyébként a prímszámok elmélete tele van bizonyítatlan sejtésekkel, éppen ezért fontos szerepet játszik a számítógép ezen a területen. Prímszámokra pedig szükség van, nem csak a matematika és informatika elméleti kérdéseiben, hanem egyre többször a gyakorlati életben is, gondoljunk csak a kriptográ ára. Tekintsük a következ® feladatot: vegyünk egy prímszámot... Nem is kell folytatnunk, hiszen már ebben a pillanatban megoldhatatlan feladat el®tt állunk. Még 2 számjegy esetén ez a probléma fejben megoldható, pár száz számjegyig számítógéppel kell dolgoznunk, pár ezer számjegy esetén már az sem segít. Tehát a számítógépes számelméletnek feladata, hogy olyan módszereket fejlesszen ki amelyek segítségével gyorsan és hatékonyan végezhet®k el a már meglév® prímalgoritmusok, illetve új algoritmusokat találjon. Ezt matematikai és informatikai eszközök felhasználásával történik, amelyek kölcsönösen hatnak egymásra. Ezalatt azt kell érteni, hogy elméleti eredményeket használunk, ahhoz, 75
76
FEJEZET 9.
PRÍMREKORDOK
hogy gyorsabb szoftvereket tudjunk fejleszteni, illetve hatékony szoftvereket fejlesztünk, matematikai problémák vizsgálatának megkönnyítésére. Prímrekordok elérésére csak akkor van esély, ha a legfrissebb matematikai és informatikai eredményeket is beépítjük szoftvereinkbe. Ha ez jól sikerül, akkor az esetleg er®sebb hardver adottsággal rendelkez® ellenfeleket is megel®zhetjük. Az igazi haszon valójában nem a megtalált nagy prímszám, hanem a hatékony algoritmusok és implementációk, amelyek remélhet®leg el®bb-utóbb beépülnek a mindennap használt szoftverekbe is. Felmerül a kérdés, hogy hogyan kerülhet be egy prímszám Yates adatbázisába, esetleg hogyan lesz világrekorder, vagy legalább hogyan lesz tagja egy Top10, vagy Top20 listának. A válasz egyszer¶: keresni kell egy számot, amely legalább 1000 decimális számjegy hosszú, be kell bizonyítani, hogy prím, és már készen is vagyunk. Természetesen manapság a titán prímek már nem számítanak kuriózumnak, s®t már évtizedekkel ezel®tt sem voltak azok, ezért 1992-ben bevezették a
gigantikus, illetve megaprím elnevezéseket. El®bbi a legalább 10 000, utóbbi a legalább 1 000 000 decimális számjegy¶ prímeket illeti. A gy¶jtemény adatbázis elemszáma 1996-ra 50 000 fölé n®tt, amelyben 2010 júniusában már több, mint 20 a megaprím, és ebb®l 3 több, mint 10 000 000 jegy¶. 1997-t®l nem csak egyedüli számokat gy¶jtenek, hanem úgynevezett
válandó formában
archi-
lév® prímszámokat. Azt, hogy kett®, vagy több prím mikor
van archiválandó formában egy nem túl egzakt de nícióval határozhatjuk meg. Tehát prímek valamely kombinációja akkor archiválandó forma,
•
ha tárgya több, mint egy matematikai témájú folyóiratban, több mint egy, különböz® szerz®csoporttól megjelent cikknek, vagy
•
tárgya 2 cikknek, amelyb®l legalább egy valamely vezet® referált folyóiratban (pl. Mathematics of Computation) jelent meg, vagy
•
tárgya akár azonos szerz®kt®l származó 4 cikknek.
Kutatásainkban gyelmünket mi az iker, illetve Sophie Germain prímekre koncentráltuk. Egy
p
prímszám
ikerprím , ha p − 2, vagy p + 2 is prím, illetve
Sophie Germain prím , ha 2p+1 is prím. 2005 és 2009 között 6 alkalommal ál-
lítottunk fel világcsúcsot, pontosan háromszor találtuk meg a világ addig ismert
9.1. A PRÍMKERESÉS VÁZLATA
77
legnagyobb iker, illetve háromszor a világ legnagyobb ismert Sophie Germain prímjét.
9.1.
A prímkeresés vázlata
Mivel a legfrissebb világrekordok elérését taglaló cikkünk még nem jelent meg a Mathematics of Computation cím¶ folyóiratban, ezért eredményeink részletezését®l jelen m¶ben el kell tekintenünk. Tehát, ebben a fejezetben csak egy vázlatát adjuk prímkeres® projektjeinknek, illetve a már publikus eredmények közlésére szorítkozunk. El®ször is generálunk olyan sorozatokat, amelynek elemei között keressük a prímrekordokat. Fontos a szitálás paramétereinek megválasztása, hiszen ezek befolyásolják többek közt a számok nagyságát, de a szitálás és prímtesztelés hatékonyságára is hatással vannak. A legfontosabb paraméterek,
h0 , e, c, R,
szerepér®l információkat kaphatunk a fejezet további részeiben. Legyen
dátusok
H = {0, 1, 2, . . . R − 1} az a halmaz, amelyb®l az úgynevezett kandi-
halmazát generáljuk. Ezek a számok lesznek az
esélyesek arra, hogy világrekorderek legyenek. A következ® polinomokkal állítjuk el® ®ket:
f1 (x) = (h0 + c · x) · 2e − 1, f2 (x) = f1 (x) + 2 = (h0 + c · x) · 2e + 1, f3 (x) = 2 · f1 (x) + 1 = (h0 + c · x) · 2e+1 − 1. Felmerül a kérdés, hogy miért van három sorozat. A válasz rövid: egyszerre
f1 , f2 , f3 polinomokkal geh ∈ H -ra azt találjuk, hogy f1 (h) f3 (h) prím esetén Sophie Germain prí-
keresünk iker, illetve Sophie Germain prímeket. Az nerált sorozatok olyanok, hogy ha valamely prím, akkor
f2 (h)
prím esetén iker, míg
met találtunk. Tehát elég az els® sorozat elemeit tesztelni, a másik kett® elemei közül csak ritkán tesztelünk, pontosan akkor, ha az els®ben prímet találtunk. Mivel a prímteszt nagyon m¶veletigényes feladat még akkor is, ha valószín¶ségi tesztet használunk, ezért el®ször san a
H
megszitáljuk sorozatainkat. Egészen ponto halmazt fogjuk szitálni, az f1 , f2 , f3 polinomok segítségével. A szitálás
kiütjük H -ból azokat az elemeket, amelyek olyan számot generálnak, amelyeknek bizonyos határig van prímfaktora. Újabb fontos
röviden itt azt jelenti, hogy
kérdés: mit jelent pontosan a bizonyos határ?
78
FEJEZET 9.
PRÍMREKORDOK
A válaszhoz gondoljuk végig, hogy mit is jelent egy sorozat szitálása egy
p
prímmel. Nagyjából azt, hogy valamilyen módszerrel kivesszük a sorozatból
azokat az elemeket, amelyek oszthatók
p-vel. Jól látható, hogy minél kisebb a p,
annál hatékonyabban szitál. Nagy szitáló prímek esetén el®fordul, hogy egyetlen elemet sem tudunk vele kiütni. A szitálást tehát addig érdemes folytatni, amíg gyorsabb, mint a valószín¶ségi prímtesztelés. Projektjeinkben úgynevezett
hármas-szitát
végeztünk. Ez a módszer az
általános szitán alapszik, amelyet három lineáris polinommal hajtunk végre. Adott
p
prímre megoldjuk az
f1 (x) ≡ 0
(mod p),
f2 (x) ≡ 0
(mod p),
f3 (x) ≡ 0
(mod p)
(9.1)
kongruenciákat. Természetesen a paramétereket úgy választjuk, hogy minden kongruenciának pontosan egy megoldása legyen. Esetünkben még arra is
f1 (h), f2 (h), és f3 (h) ne legyen osztható a 2, 3, 5, 7, 11, 13 prímek egyikével sem egyetlen h ∈ H esetén sem. Így projektjeinkben az els® szitáló prím mindig a 17 volt. Tehát ha egy h ∈ H szám megoldása a (9.1) kongruenciák valamelyikének, akkor H -ból egyszer¶en kitöröljük a
ügyeltünk, hogy
{h, h + p, h + 2p, . . . } elemeket. A következ® fontos kérdés, amely ezen a ponton felmerül a következ®: mi történik, ha például egy szita nem üti ki
H -ból,
h∈H
szám olyan, hogy az
viszont az
f3 -mal
f1 , f2
polinommal végzett
végzett igen? A válsz: sajnos ekkor
elvesztünk egy olyan számot, amelynek esélye van arra, hogy ikerprím legyen. Miért használunk akkor hármas szitát? Azért, mert hatékonyabb, mint a kettes szita, továbbá ha veszítünk is valamennyi iker, illetve Sophie Germain prímet a szitafolyamat során, még mindig
jó esélyünk marad arra, hogy végül találjunk ilyen kombinációkat. Utóbbi állításunkat számításokkal is alá tudjuk támasztani, amelyek a következ® fejezetben találhatók. Ha a szitálást befejeztük, következhet a kandidátusok tesztelése, tehát végigolvassuk
H
maradék elemeit, és ha azt találjuk, hogy
f1 (h)
valószín¶leg prím,
9.2. A PARAMÉTEREK VÁLASZTÁSA
akkor teszteljük
79
f2 (h)-t és f3 (h)-t is. Az ellen®rzéshez Miller-Rabin-tesztet hasz-
nálunk, amely igen gyors, viszont amíg az általánosított Riemann-sejtés nem bizonyított, addig ezen prímteszt eredménye nem fogadható el bizonyításnak. Tehát, a nem determinisztikus tesztelés után a megtalált számaink prímségének bizonyítását még el kell végezni. Ez a Riesel-teszt segítségével történik
f3 (h)
esetében és a Proth-teszttel
f2 (h)
f1 (h),
esetében.
Utóbbi teszt elmélete egyszer¶, hiszen csak a névadó által bizonyított tétel feltételeinek teljesülését kell ellen®rizni programmal. Ezzel ellentétben a Rieselteszt elmélete sokkal bonyolultabb, ráadásul beleszól a prímkeres® projekt pa ramétereinek választásába is. Itt kötelességünk megemlékezni egy érdekes tényr®l. Azt megszokhattuk a tudomány-történelemben, hogy vannak olyan polihisztorok, akik jelent®s eredményekkel rendelkeznek olyan területen is, amely nem szorosan kapcsolódik saját
szakmájukhoz, Francois Proth azonban mindenkin túltesz, hiszen még iskolába sem járt, földm¶vel® volt. Tehát jogosan mondhatjuk, hogy munkássága a
józan paraszti ész diadala. A Proth-teszt alapjául szolgáló tételét 1878-ban publikálta:
9.1. tétel.
(Proth tétel) Minden
páratlan, és
2n > k ,
ha létezik
a
N = k · 2n + 1
természetes számra, ahol
k
egész úgy, hogy
a(N −1)/2 = −1
(mod N ),
akkor N prím.
f1 (h), f3 (h) esetében a Riesel-tesztet használjuk, amelyet Hans Riesel publikált [21] dolgozatában 1969-ben. Az szakirodalomban ezzel az eljárással Lucas LehmerRiesel-teszt néven is találkozhatunk, ami nem véletlen, a módszer az úgynevezett
Lucas sorozatokat
használja egy
N = k · 2n − 1 (k < 2n )
alakú
szám prím mivoltának bizonyításához. A Riesel-tesztr®l nem csak bonyolultsága miatt szólunk részletesebben az alábbiakban, hanem mert szeretnénk kiemelni, hogy ebben a módszerben is felbukkannak a kvadratikus testek és algebrai egészeik.
9.2.
A paraméterek választása
A világban sok kutatócsoport foglalkozik nagy prímszámok keresésével. Természetesen nem mindenki a fent vázolt módszert használja, még iker és Sop-
80
FEJEZET 9.
PRÍMREKORDOK
hie Germain prímek esetében sem. Van egy olyan eljárás, amelynek során a prímvadász fejleszt egy szoftvert, amelyet bárki letölthet az Internetr®l és fut tathat saját gépén. Ezek a programok elvégzik egy adott intervallum szitálását,
hangya )
és a megfelel® valószín¶ségi teszteket. A letölt® ( után visszaküldi az eredményt a vadásznak. Ha egy
a program futása
szerencséje van, akkor talált
valószín¶leg iker, vagy Sophie Germain prímet. A prímség bizonyítását
a vadász végzi el. Ennek a módszernek a problémája saját véleményem szerint az, hogy a vadász ki van szolgáltatva a hangyáinak, emiatt egy prímkeres® projekt sikerességénél megn® a véletlen szerepe. Az kétségtelen, hogy ha sok hangya hajlandó dolgozni, akkor sok processzort be tudnak vonni a munkába, ami szitálásnál és valószín¶ségi teszteknél is hasznos. F® hátrány viszont, hogy 50 százalékban osztozni kell a dics®ségen, hiszen az felerészben a számokat megtaláló hangyát illeti. Összefoglalva, projektjeinknél azt az utat választottuk, hogy magunk fejlesztette szoftverekkel magunk végeztük a projektjeink minden lépését. Természetesen, hogy sikert érjünk el, szükségünk volt pontos matematikai számításokra, amelyek mentén
be tudtuk l®ni a projekt fontos paramétereit, továbbá nagyon gyors szoftverekre, amelyeket Járai professzor útmutatásai alapján el is tudtunk készíteni. A valóság minket igazolt, hiszen 2005-ben b® két hét alatt, amelybe nincs beleszámolva a szoftverfejlesztés ideje, megtaláltuk azt a világrekorder ikerprímet, amely 51 799 decimális számjegy hosszú volt és majdnem másfél évig vezette a világranglistát. Meg kell jegyezni, hogy számításainknál felhasználtunk olyan eredményeket is, amelyeket sejtésként tart számon a számelmélet tudománya, így jogosan merülhet fel a kérdés, hogy lehet-e egy tudományos projektet egy, vagy több sejtésre alapozni. Az alábbiakban közölt számítások és megfontolások bizonyítani fogják, hogy az elért világrekordjaink nem a véletlennek köszönhet®k.
9.2.1.
A kandidátusok halmazának meghatározása
Fontos, hogy úgy válasszuk meg a szitálás paramétereit, hogy hatékony legyen a hármas szita, de megfelel®en nagy esélyünk maradjon iker, vagy Sophie Germain prímek megtalálására. Megfelel®en nagy esély alatt azt értjük, hogy a vizsgált halmazban legyen az iker és Sophie Germain prímek el®fordulásának várható
9.2. A PARAMÉTEREK VÁLASZTÁSA
értéke egynél nagyobb. Ezt az
R
81
érték határozza meg, hiszen ez a paraméter
szabja meg a kandidátusok kezdeti számát. Világos, hogy ha kor jelent®sen lecsökkenhet az esélyünk arra, hogy legyen a
H
R
túl kicsi, ak halmazban olyan
kandidátus, amely iker, vagy Sophie Germain prímet generál. Ha
R
túl nagy, akkor a tesztprogramok futási ideje lesz végrehajthatatlanul nagy. A keresett prímkombinációk várható értékének kiszámítását az alábbi fejezetekben részletezzük. A
c
paraméter értékét úgy kapjuk, hogy egyszer¶en összeszorozzuk azokat a
prímeket, amelyekkel nem szeretnénk szitálni. Tárgyalt projektjeinknél a
c = 2 · 3 · 5 · 7 · 11 · 13 = 30030 konstanst használtuk. Könnyen ellen®rizhet®, hogy ekkor az egész számok egyike sem lesz osztható
2, 3, 5, 7, 11, 13-mal
f1 (h), f2 (h), f3 (h) h ∈ H értékekre,
tehát
c·x≡0 ha
p
c-nek. A h0 értéket 2, 3, 5, 7, 11, 13
faktora
kongruenciáknak a
(mod p),
pedig úgy kell megállapítanunk, hogy a 9.1 modulusokkal nulla, a többi prímre pontosan
egy megoldása legyen. Az
e paraméterrel határozzuk meg a keresett prímszámok nagyságát. e érté-
kének kiválasztásakor bizonyos programozástechnológiai szempontokat is gyelembe kell vennünk, amelyeket jelen m¶ keretei között nem tárgyalunk. A Riesel-teszt elvégzéséhez a tesztelt számnak rendelkeznie kell bizonyos feltételekkel, amelyeket gyelembe kell vennünk az
e és a h0
tásakor. Egész pontosan teljesülnie kell az úgynevezett a vizsgálandó
N = k · 2n − 1
paraméterek kiválasz-
Lucas kritériumnak
alakú egész számokra. Ez azt jelenti, hogy léteznie
kell egy Lucas sorozatnak a következ® feltételekkel:
v0 vn−2 ≡ 0
adott,
(mod N )
vi = vi2 − 2
akkor és csak akkor, ha
x
helyére szitálás után
természetesen
e
felel meg.
N
prím.
N = k · 2n − 1 képletben k = h0 + c · x, valamilyen h ∈ H érték kerül. Az n kitev®nek
Vegyük észre, hogy esetünkben az ahol
és
82
FEJEZET 9.
9.2.2.
PRÍMREKORDOK
A Riesel-teszt
[21] munkájában Riesel adott egy módszert, amely segítségével bizonyos feltételek teljesülése mellett található olyan Lucas sorozat, amely eleget tesz a Lucas kritériumnak. Ennek megértéséhez tekintsünk egy tet, ahol
D
√ Q( D) valós kvadratikus tes-
egy négyzetmentes természetes szám. Ekkor, ahogy láttuk az els®
fejezetben,
√ √ Q( D) = {u + v D | u, v ∈ Q}.
A kvadratikus testekkel kapcsolatos további fogalmak, mint például konjugált, vagy norma, szintén az els® fejezetben találhatók, itt nem részletezzük. Jelölje
√ Q( D)
ID ,
algebrai egészeit
ekkor láttuk, hogy
D ≡ 2, 3 (mod 4)
esetén
√
ID = {m + n D | m, n ∈ Z}, és
D ≡ 1 (mod 4)
esetén
ID
√ 1+ D = {m + nω | m, n ∈ Z}, ω = . 2
Tudjuk továbbá, hogy
ID -ben
végtelen sok egység van, továbbá ezek közt
létezik egy olyan, amely hatványai segítségével el®állítható az összes egység. Ezt a bizonyos alapegységet az eredeti cikknek megfelel®en tétele, amelynek feltételeit
9.2. tétel.
h0
és
e
ε-nal jelöljük. Riesel
választásakor be kell tartanunk, a következ®:
n ≥ 2 egész, k páratlan egész, k < 2n , N = k·2n −1, r =| a − b D |, ahol a, b ∈ Z, √ 2 a+b D α= , r D = −1, és N r a2 − b2 D = −1 N r D ahol N a Jacobi szimbólumot jelenti. Ekkor N prím mivoltának szükséges és 2
Tegyük fel, hogy
2
elégséges feltétele, hogy
vn−2 ≡ 0 ha
vi =
vi2
−2
és
k
v0 = α + α
−k
.
(mod N ),
9.2. A PARAMÉTEREK VÁLASZTÁSA
83
α egység ID -ben, tehát az ε (s = 1, 2, 3, . . . ). Az is bizonyítható, hogy
Könny¶ belátni, hogy
alapegység valamely
hatványa
ha
ε
s-edik
el®áll
√ 2 a+b D
ε=
r
s páratlan. Ebben az esetben az α = ε választás a legegyszer¶bb, α = ε2 választást célszer¶ alkalmazni.
alakban, akkor különben az Tehát a
h0 paraméter úgy fogható fel, mint egy
nomhangoló eszköz, amely nem befolyásolja a keresend® prímszámok nagyságrendjét, s®t a generált sorozatokban el®forduló prímkombinációk várható számát sem, viszont szükséges ahhoz, hogy a(z) (9.1) kongruenciák megfelel® megoldhatósága mellett biztosítsa azt, hogy a Riesel-teszt feltételeinek megfelel®
k
értéket megkapjuk.
Példaképpen tekintsünk egy konkrét esetet. 2009-ben végrehajtott prímkeres® projektünkben az
√ Q( 13)
e = 253824
paraméterrel dolgoztunk, a Riesel-teszthez a
kvadratikus testet használtuk. Tehát, hogy
2, 3, 5, 7, 11, 13
modulussal
a(z) (9.1) kongruenciáknak ne legyen megoldása, egyéb prímmodulusokra pedig pontosan egy, a következ®knek kell teljesülnie:
h0 ≡ 0, 1
(mod 2),
h0 ≡ 0
(mod 3),
h0 ≡ 0, 2
(mod 5),
h0 ≡ 0, 2, 3, 5
(mod 7),
h0 ≡ 0, 1, 3, 4, 5, 6, 7, 8
(mod 11),
h0 ≡ 0, 2, 3, 4, 5, 6, 8, 9, 10, 11 Kapjuk továbbá, hogy a tétel feltételei, ha
h0
k
értékre csak abban az esetben teljesülnek a Riesel
a következ® számok valamelyikével reprezentálható:
h0 ≡ 3, 6, 8 Ha a
2, 3, 5, 7, 11, 13
(mod 13).
(mod 13).
1, 0, 0, 0, 0, 3 maradékokkal h0 = 5775 értéket adja.
modulusokkal és rendre az
molunk, akkor a kínai maradéktétel a
szá-
84
FEJEZET 9.
9.3.
PRÍMREKORDOK
Az
elejtett Sophie Germain és ikerprímek várható száma
Az els® kérdés megválaszolásához tekintsük a számelméletben jól ismert prímszám tételt, amely azt állítja, hogy
π(x) ∼
x , ln(x)
amelyb®l következik, hogy annak esélye, hogy egy
n∈N
szám prím:
1 . ln(n) h ∈ H
f2 (h) prím legyen, nem független valószín¶ségi események, tehát annak esélye, hogy f1 (h) és f2 (h) ikerprím legyen, Sajnos az, hogy
egészre
f1 (h)
és
igen rosszul közelíthet® a következ® képlettel:
1 . ln(f1 (h)) ln(f2 (h)) Tökéletesíteni tudjuk a fenti formulát egy 1962-ben publikált eredmény segítségével
([56]).
Annak ellenére, hogy a cikkben taglalt állítás, amely
Horn-sejtésként
Bateman-
vonult be a számelmélet történelmébe, a mai napig nem bi-
zonyított, a gyakorlatban igen jól m¶ködik. Ezt a tényt bizonyítja prímkeres® projektünk is, elég csak összehasonlítanunk az alábbiakban közölt elméleti számítások eredményét a számítógépes eredményekkel.
Bateman-Horn-sejtés.
Legyenek
f1 (x), f2 (x), . . . , fs (x)
linomok, egész együtthatókkal és pozitív f®együtthatóval. Ha
1
egészek számát, amelyekre
π(r) ≈ Cf1 ,...,fs ·
f1 (n), f2 (n), . . . , fs (n)
irreducibilis po-
π(r)
jelöli azon
mind prím, akkor
r X 1 1 · , deg(f1 (x)) · · · deg(fs (x)) n=2 (ln(n))s
ahol
Cf1 ,...,fs
−s Y w(p) 1 = 1− · 1− , p p p∈P
(9.2)
9.3. AZ ELEJTETT SOPHIE GERMAIN ÉS IKERPRÍMEK VÁRHATÓ SZÁMA85
ahol
w(p)
jelenti az
f1 (x) · · · fs (x) ≡ 0 kongruencia
x
(mod p)
megoldásainak számát.
(9.2) formulában az 1 − w(p)/p kifejezés annak a valószín¶sége, hogy f1 (n), f2 (n), . . . , fs (n) egészek egyike sem osztható p-vel, továbbá (1 − 1/p)s a valószín¶sége annak, hogy s darab egész szám egyike sem osztható p-vel. Esetünkben tehát a fentiek segítségével a következ® formulával becsülhetjük meg azt, hogy milyen valószín¶séggel lesz
f1 (h)
és
f2 (h)
egyszerre prím:
Cf1 ,f2 . ln(f1 (h)) ln(f2 (h))
(9.3)
Mivel a szitálást lineáris polinomokkal végezzük, ezért
Cf1 ,f2
értékét könnyen
meghatározhatjuk a
Cs =
Y 1 − s/p (1 − 1/p)s p>s
kifejezésb®l. Ilymódon megbecsülhetjük, hogy a szitálás megkezdése el®tt várhatóan hány darab iker, és Sophie Germain prím található a generált sorozatainkban. Ehhez tekintsük a következ® számolást. Legyen
C=
1 1− 2
−2 −2 −2 −2 −2 −2 1 1 1 1 1 · 1− · 1− · 1− · 1− · 1− . 3 5 7 11 13
Figyelembe vettük, hogy olyan polinomokkal dolgozunk, amelyek megfelel® helyettesítési értékei nem oszthatók az els® hat prímmel. Tehát kapjuk, hogy
Cf1 ,f2 = C ·
Y 17≤p∈P
1 − 2/p (1 − 1/p)
2,
amelyb®l következik, hogy
Cf1 ,f2 =
1 1− 2
−2 −1 2 2 2 2 2 · 1− · 1− · 1− · 1− · 1− ·C2 , 3 5 7 11 13
86
FEJEZET 9.
PRÍMREKORDOK
ahol
C2 = 0.6601618158468695739278121100145... az úgynevezett
ikerprím konstans . Végül a következ® eredményt kapjuk: Cf1 ,f2 ∼ 26.69987788. πf1 ,f2 (a, b) várható értékének kiszámolására [a, b)-beli száf1 (h) és f2 (h) egyszerre prím. Ezt a következ®képpen tehetjük
Most rátérhetünk a mokra, amelyekre meg:
Z πf1 ,f2 (a, b) ∼ Cf1 ,f2 · a
b
du . ln(f1 (h)) ln(f2 (h))
Mivel az f1 és f2 értékek nagyok, így logaritmusuk majdnem konstans. Ezt felhasználva alkalmazhatjuk a Simpson formulát, amelyb®l kapjuk, hogy
πf1 ,f2 (a, b) ∼ Cf1 ,f2 · ·
R · 6
1 1 4 + + a+b ln(f1 (a)) ln(f2 (a)) ln(f1 ( a+b ln(f (b)) ln(f2 (b)) 1 2 )) ln(f2 ( 2 ))
! .
R = 233 , h0 = 5775, c = 30030, e = 171960 paramétereket használtuk, így a szitálás megkezdése el®tt a H elemeib®l A 2005-ös prímkeres® projektben az
generált sorozatokban lév® ikerprímek várható számát a
233 · 6 · (0.7037705515 + 4 · 0.7034892594 + 0.7034810790) · 10−10 πf1 ,f2 (0, R) ∼ 26.69987788 ·
számolással becsülhettük, azaz
πf1 ,f2 (0, 233 ) ∼ 16.13558453 Természetesen ugyanennyi Sophie Germain prím jelenléte is várható volt. Ez azt jelenti, hogy várhatóan minden
532.359.679-ik (R/πf1 ,f2 (0, R)) szám lesz
iker (Sophie Germain) prím a megfelel® halmazban. 2009-ben, a "Cell processor" projektben a következ® paraméterekkel dolgoztunk:
R = 235 , h0 = 5775, c = 30030, e = 253824.
A fenti gondolatmenetet
9.4. A SZITÁLÁS RÉSZLETEI
87
követve kiszámolhatjuk, hogy ebben az esetben
233 · 6 · (0.3230285819 + 4 · 0.3229360126 + 0.3229334683) · 10−10 , πf1 ,f2 (0, R) ∼ 26.69987788 ·
azaz
πf1 ,f2 (0, 235 ) ∼ 29.62755270 iker, és ugyanennyi Sophie Germain prímre számíthattunk a szitálás el®tt. Ez azt jelenti, hogy minden
1.159.722.462-ik
szám volt várhatóan iker, vagy Sop-
hie Germain prím. Megjegyezzük, hogy mindkét projektünk sikerrel zárult, és összesen hat világrekordot állítottunk fel 2005 és 2009 között. Utóbbi projekt részletei ezen m¶ írásakor még nem publikusak, így csak az el®bbi eredményeinek ismertetésére szorítkozunk a kés®bbiekben.
9.4.
A szitálás részletei
El®ször el®állítjuk Eratosztenészi szitával a fels® korlátját jelöljük
SM -mel.
Az, hogy
kis prímek halmazát, amelynek
SM
értékét mekkorára választjuk,
függ többek között az implementációtól és hardver feltételekt®l is. Például, ha rendelkezésünkre áll egy grid, érdemes párhuzamosítani az eljárást, de ez csak akkor éri meg, ha a szitálandó tartomány
elfér minden processzor operatív memóriájában. Tehát a kis prímekkel való szitálást egy nagy teljesítmény¶ processzorral szerelt gép végzi. A kisprím szitát addig végezzük, amíg annyira redukálódott a kandidátusokat generáló elemek száma, hogy beférnek a grides gépek operatív memóriájában is. A 2005-ös projektben
SM
300 millió körül volt, és
körülbelül 50 percet vett igénybe a kisprím szita, amely hozzávet®leg ra csökkentette a kandidátusok számát. Tapasztalatok szerint általában
1/3001/1000
tömörít® faktorig érdemes a kis prímekkel szitálni. 2005-ben az amszterdami szuperszámítógépen, ahol
jól el voltunk látva gyors és viszonylag nagy opera tív memóriájú processzorokkal, megérte áttérnünk el®bb a paralel számolásra.
1/1000-rel számolunk. H elemeit egy ST bitvektornak feleltetjük meg olymódon, hogy H elemei ST indexei legyenek. Kezdetben ST minden eleme 1-re van állítva. Ha azt találjuk,
A kés®bbiekben
88
FEJEZET 9.
PRÍMREKORDOK
f1 (h), f2 (h) vagy f3 (h) számnak van egy 17 ≤ p ≤ SM prímfaktora valamely h ∈ H értékre, akkor beállítjuk az ST [h], ST [h+p], ST [h+2p], . . . , ST [h+ qp] biteket 0-ra, amíg h + pq < R. A kisprím szita után tehát körülbelül ST minden ezredik bitje marad 1. Tárhelyet spórolhatunk, ha ekkor az 1-es bitek indexeit, azaz azokat a h ér-
hogy
tékeket, amelyeknek még van esélye, hogy prímszámot generálhatunk bel®lük, áttöltjük egy
ST H
ST H
vektorba, amely el®jel nélküli egészeket képes tárolni. Az
már nem bitvektor, de még így is hozzávet®leg 30-szor kisebb, mint
ST .
Tehát a kisprím szita célja, hogy el®segítse a párhuzamosítás lehet®ségét akár kisebb teljesítmény¶ processzorokon is. A továbbiakban tegyük fel, hogy van egy
LP
jelölje
a
n
processzorból álló gridünk, és
nagy prímek halmazát, azaz
P = {p|p ∈ P ∧ SM < p ≤ M } , ahol
P
a prímszámok halmazát jelöli,
M
a legnagyobb prím amellyel szitálást
ST H -ból, továbbá egy P ST nevezni. Minden kiosztott P ST
végzünk. Minden processzor megkap egy másolatot tömböt, amelyet prímszita táblának is szokás különböz® prímeket tartalmaz
LP -b®l. P ST
nagysága függ az operatív memó-
riák méretét®l. A továbbiakban jelölje
ST Hi
az
ST H
másolatát, míg
P STi
a prímszita
táblát, amelyet az i. processzor kapott. Tehát minden processzor kiszitálja saját
ST H
P ST -jében talált prímekkel. Az elv ugyanaz, miszerint h ∈ ST H értéket ST H -ból, ha f1 (h), f2 (h), vagy f3 (h)
tömbjét, a saját
üssünk ki minden számnak van p ∈ LP prímfaktora, de az eltávolítás folyamata más.
Valójában a nagy prímekkel nem szitálunk közvetlenül, azaz nem ütjük ki a
ST Hi -b®l, hanem eltároljuk egy STi∗ tömbben. Gyakorlati∗ ∗ lag az STi egy részhalmaza H -nak, amelyet kés®bb kivonunk bel®le. Amint STi 6 ∗ számossága elér egy határt (∼ 10 ), rendezzük STi elemeit és bináris kereséssel ∗ megkeressük ®ket ST Hi -ben. Ha STi egy elemét megtaláljuk ST Hi -ben, akkor ∗∗ ∗∗ eltároljuk az STi tömbben. Ha STi számossága is elér egy alkalmas határt 6 (∼ 10 ), akkor rendezzük és elemeit kitöröljük ST Hi -b®l. Amikor az i. processzor minden P STi -beli prímmel befejezte a szitálást, akkor aktualizáljuk ST H -t, azaz kitöröljük azokat az elemeket, amelyek ST Hi -ben megfelel®
h
számot
nincsenek már benne. Ez pontosan azt jelenti, hogy végül kizárólag azok a számok maradnak
ST H -ban, amelyek megtalálhatók minden ST Hi -ben, 1 ≤ i ≤ n.
9.5. A SZITÁLÁS HATÉKONYSÁGÁNAK ELEMZÉSE
Ezután, ha szükséges, a
P STi
tömböt újratöltjük
89
LP -b®l, ST Hi
ismét
ST H
lesz, és kezd®dik újra a szitálás. A szitálás m¶veletét addig érdemes folytatni, amíg gyorsabban csökkenti a kandidátusok számát, mint a nem determinisztikus prímtesztelés.
9.5.
A szitálás hatékonyságának elemzése
Térjünk rá most a második kérdés vizsgálatára. Természetesen a szitálástól azt várjuk, hogy a vizsgált számhalmazokban megnövekedjen az iker-, és a Sophie Germain prímek s¶r¶sége. Azt láttuk, hogy a hármas szita kiüthet, és nagy valószín¶séggel ki is üt iker-, és Sophie Germain prímeket, tehát szeretnénk tudni, hogy mennyi az esélye annak, hogy maradnak ilyen formációk a szitálás után. A Bateman-Horn-sejtésnek köszönhet®en tudunk következtetni a szitálás tömörít® hatásának mértékére. Nevezetesen, ha az
lunk, akkor az
s
a≤p
prímekkel szitá-
elem¶ prímformulák s¶r¶sége a következ® faktorral n®:
qfa,b = 1 ,...,fs
1
Y a≤p
1−
w(p) p
.
Tehát ezzel a faktorral csökken a kandidátusok száma, és természetesen ugyanennyivel csökken a prímtesztelésre fordítandó CPU-id® is. Mivel mi lineáris polinomokat használtunk a szitáláshoz, esetünkben a tömörít® faktor megállapítása így történik:
qsa,b =
Y a≤p
1 . 1 − ps
(9.4)
(9.4) szorzat értékének közelít® meghatározásához a
p < L ∼ 1 000 000 értékekre pontos számolást végeztünk, majd a maradék részt a
(ln(L)/ ln(b)) formulával közelítettük, ahol a relatív hiba
s
0.1%
alatt van.
90
FEJEZET 9.
PRÍMREKORDOK
Tegyük fel most, hogy csak dupla szitát végzünk, mondjuk ikerprímekre. Ekkor a tömörít® faktor
q217,M =
Y 17≤p<M
1 1−
2 p
∼
1 1 − 17≤p
Y
·
2 p
ln(L) ln(M )
2 (9.5)
lenne, ami azt jelenti, hogy a szitálás után a kandidátusok száma re csökkenne, azaz minden
t-edik
t=
szám lenne
valószín¶leg prím, ahol
R q217,M
R-r®l R/q217,M -
· πf1 ,f2 (0, R)
.
Igen, de a hármas szita csökkenti az iker, és Sophie Germain prímek várható értékét az ® tömörít® faktorával, amely így számolható:
q317,M =
Y 17≤p<M
1 1−
3 p
∼
1 1 − 17≤p
Y
3 p
·
ln(L) ln(M )
3 .
(9.6)
(9.5) és (9.6) összefüggést gyelembe véve kapjuk, hogy az iker, és Sophie Germain prímek várható értéke a hármas szita:
πf1 ,f2 (0, R) ·
2005-ben a tervezett szitahatár
q217,M q317,M
M = 248
.
(9.7)
volt, így a szitálás után az iker, és
Sophie Germain prímek el®fordulásának várható értéke
1.367684186 volt. A valóság minket igazolt, hiszen három esetben megtaláltunk olyan iker és három alkalommal olyan Sophie Germain prímet, amelyek megtalálásuk pillanatában a világon a legnagyobb ismert számkombinációk voltak. A konkrét értékek az alábbi táblázatban tanulmányozhatóak:
9.5. A SZITÁLÁS HATÉKONYSÁGÁNAK ELEMZÉSE
91
Szám
Számjegy
Dátum
Típus
16869987339975 · 2171960 ± 1
51779
2005
Iker
137211941292195 · 2171960 − 1
51780
2006
Sophie Germain
100314512544015 · 2171960 ± 1
51780
2006
Iker
194772106074315 · 2171960 ± 1
51780
2006
Iker
620366307356565 · 2253824 − 1
76424
2009
Sophie Germain
648621027630345 · 2253824 − 1
76424
2009
Sophie Germain
Befejezésül tekintsünk egy kérdést, amelyet gyakran feltesznek a témában: eredményeink mennyire közelítik a
valóságot, hiszen számításainkat bizonyos esetekben sejtésekre alapoztuk. Az alábbiakban közlünk néhány konkrét adatot a 2005-ös projektünkb®l, amelyek bizonyítják számításaink pontosságát. A kandidátusok száma kezdetben
R = 233
volt. El®ször az úgynevezett "kis
prímekkel" szitáltunk. Ezek közül a legnagyobb
SM = 305 020 993
volt. Ezen
prímek esetén a hármas szita tömörít® hatása számításaink szerint
q317,SM ∼
Y 17≤p≤1 000
1 1− 033
3 p
·
ln(1 000 033) ln(305 020 993)
3 .
Tehát a kis prímekkel való szitálás után a kandidátusok számának várható
92
FEJEZET 9.
értéke az elmélet szerint
R q317,SM
volt. A valóságban mi az elméleti érték és a
PRÍMREKORDOK
∼ 27 344 542
27 347 222 kandidátust számoltunk, ami azt jelenti, hogy valóság közt az eltérés kevesebb, mint 0.01%.
10. fejezet
Elliptikus görbék 10.1.
Alapgondolatok
Elliptikus görbéket
általában különböz® egyenletek gra konjait alkotó pontok
halmazaként szoktak de niálni. Mi gyelmünket ezek közül kizárólag az úgynevezett
Weierstrass egyenletekre
fogjuk koncentrálni. Ezek
y 2 = x3 + ax + b alakú kifejezések, ahol milyen
K
a és b konstansok. Természetesen az a tény, hogy x, y, a, b
halmaz eleme, befolyásolja az adott elliptikus görbe tulajdonságait.
K az R, C, Q, Fq testek valamelyikéb®l kerül ki, ahol q = pr és p 6= 2, 3. Mivel jelen írásm¶ célja, az hogy az elliptikus görbék
Általában
prím-
hatvány
szám-
elméleti és kriptográ ai jelent®ségét vizsgálja, ezért els®sorban a véges testeken de niált görbékre gyelünk, annak ellenére, hogy a legújabb kutatások már a racionális számtest felettiek fontosságára is rámutatnak. Nézzük ezek után a pontos de níciókat, ahol az elliptikus görbéket tulajdonképpen testek elemeib®l képzett párok halmazának tekintjük. Legyen
K
tetsz®leges, nem
2,
nem
3
karakterisztikájú test és
w(x) = x3 + ax + b ∈ K[x] olyan harmadfokú polinom, amelynek gyökei különböz®ek. 93
94
FEJEZET 10.
10.1. de níció. az
E(K)
K
feletti elliptikus görbén azoknak az
ELLIPTIKUS GÖRBÉK
(x, y) ∈ K×K
pontoknak
halmazát értjük, amelyekre
y 2 = x3 + ax + b teljesül, kiegészítve ezt egy úgynevezett
végtelen távoli
O
elemmel.
Tehát
E(K) = {O} ∪ (x, y) ∈ K × K | y 2 = x3 + ax + b . Azt, hogy
w(x)-nek
három különböz® gyöke legyen, a
4a3 + 27b2 6= 0 feltétellel biztosíthatjuk. Megmutatható, hogy ha gyökei
r1 , r2 , r3 ,
w(x)
harmadfokú polinom
akkor a diszkriminánsa
2 ((r1 − r2 )(r1 − r3 )(r2 − r3 )) = − 4a3 + 27b2 . A de nícióban kizártuk a
2
és
3
karaktersztikájú véges testeket is. Ezeknél
a struktúráknál a zéróval való osztás okozhat gondot, amelyet az úgynevezett
általánosított Weierstrass egyenletekkel
lehet kiküszöbölni:
y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 . Legyen
K = R.
Ekkor
E(K)
vagy három, vagy egy helyen metszi az
x-
tengelyt. Az el®bbi esetre a 10.1. ábrán, utóbbira a 10.2. ábrán láthatunk példát.
10.1.1.
Csoport törvény
Nem titkolt célunk, hogy
E(K)
pontjai közt alkalmas m¶veletet bevezetve cso-
portot kapjunk. A megfelel® módon megválasztott elliptikus görbés csoportok kiválóan alkalmazhatók prímfaktorizációnál, illetve a kriptográ ában, s®t a napjainkban leghatékonyabb prímtesztel® algoritmusoknál. A konstrukció azon észrevételen alapul, hogy a fenti feltételekkel adott elliptikus görbék rendelkeznek azzal a tulajdonsággal, hogy ha egy egyenes két különböz® pontban metszi az elliptikus görbe gra konját, akkor biztosan metszi egy harmadik pontban is.
P, Q két különböz® pont E(K)-ban, amelyekre P és Q nem egymás tükörképei az x-tengelyre vonatkozóan. A P, Q pontokon átmen® egyenes E(K)t egy harmadik pontban is metszi, jelöljük ezt P ∗Q-val. P ∗Q-nak az x-tengelyre Legyen
10.1. ALAPGONDOLATOK
10.1. ábra. Az
95
y 2 = x3 − 10x + 10
10.2. ábra. Az
y 2 = x3 − 3x + 3
egyenlettel adott elliptikus görbe.
egyenlettel adott elliptikus görbe.
P + Q. Ha P = Q, akkor a P, Q pontokon átmen® egyenest a P -n átmen® érint®jével helyettesítve a további metszéspont P ∗ P és P + P . A P ∈ E(K) pont tükörképe −P. A P -n és (Q =)−P -n átmen® egyenes mer®leges az x-tengelyre. Azt mondjuk, hogy a végtelen távoli pontban, O -ban metszi a való tükörképe
96
FEJEZET 10.
ELLIPTIKUS GÖRBÉK
P ∗ (−P ) = O, és P + (−P ) = O. Továbbá, ha P = (x, y), akkor −P = (x, −y). El®ször legyenek P = (x1 , y1 ), Q = (x2 , y2 ), különböz® E(K)beli pontok, úgy hogy egyikük sem a O elem. Tegyük fel továbbá, hogy x1 6= x2 , azaz a P, Q ponton átmen® y = αx + β egyenes (nem mer®leges az x-tengelyre). Ekkor görbét,
y2 − y1 , β = y1 − αx1 , x2 − x1
α= amib®l kapjuk, hogy
y = α(x − x1 ) + y1 . Szeretnénk megkeresni az egyenes harmadik metszéspontját a görbével. Le-
P ∗ Q = (x3 , y3 ) (= (x3 , αx3 + β)).
gyen
Meg kell oldanunk az
(αx + β)2 = x3 + ax + b harmadfokú egyenletet. Ez általában nem könny¶, de most felhasználhatjuk, hogy három különböz® gyök van, ráadásul ezekb®l kett®t ismerünk. Ha a három
x1 , x2 , x3 ,
gyök
az egyenletet az
x3 − α2 x2 + (a − 2αβ)x + (b − β 2 ) = 0 alakba tudjuk írni, és gyelembe véve, hogy a bal oldali polinom ekvivalens az
(x − x1 )(x − x2 )(x − x3 )
polinommal, kapjuk, hogy
x1 + x2 + x3 = α 2 , amelyb®l rögtön adódik, hogy
x3 = α2 − x1 − x2 , és
y3 = α(x1 − x3 ) − y1 , mivel
P + Q = (x3 , −y3 ),
tehát
P
és
Q
összege könnyen kiszámítható.
Most vizsgáljuk azt az esetet, amikor
x1 = x2
és
y1 6= y2 .
ponton átmen® egyenes függ®leges, tehát az elliptikus görbét a azaz
O-ban,
tehát ekkor
P + Q = O.
Ekkor a
∞-ben
P, Q
metszi,
10.1. ALAPGONDOLATOK
97
P = Q = (x1 , y1 ). Az E(K) görbe P pontbeli y = αx + β α = dy/dx dierenciálhányados kiszámításával határozhatjuk meg.
Most legyen érint®jét az
Implicit dierenciálással:
2ydy = (3x2 + a)dx, tehát
dy 3x2 + a 3x2 + a = |x1 ,y1 = 1 = α. dx 2y 2y1
Mi a helyzet
y1 = 0
esetén? Ekkor az érint® egyenes függ®leges, tehát a
végtelenben metszi a görbét, azaz most is azt kapjuk, hogy továbbiakban tegyük fel, hogy most is
y1 6= 0.
A
P, Q
y = α(x − x1 ) + y1 , viszont csak x1 multiplicitása kett®, hiszen
Szerencsére
P + Q = O.
A
ponton átmen® egyenes egyenlete
egy gyök ismert, nevezetesen érint®nk van a
P = Q
x1 .
pontban.
Tehát az el®bbihez hasonló számolással kapjuk, hogy
x3 = α2 − 2x1 , és
y3 = α(x1 − x3 ) − y1 . Q = O. Ez azt jelenti, hogy a P, Q ponton átmen® egyenes függ®leges és pontosan P x-tengelyre vett tükörképében metszi a görbét. Tehát a P +O = P eredményt kapjuk. Természetes módon ezt alkalmazhatjuk a P = Q = O esetre is, azaz O + O = O. Bevezetjük a következ® jelölést n ∈ N-re: Végül tegyük fel, hogy
nP = P + P + . . . P , {z } | n -szer
és
−nP = (−P ) + (−P ) + · · · + (−P ) . {z } | n -szer
A
P ∈ E(K)
n-edrend¶nek nP = O.
pontot
szám, amelyre
Hasonlóan gondolkozhatunk, ha
nevezzük, ha
n
az a legkisebb pozitív egész
P, Q koordinátái és az a, b paraméter tetsz®2, vagy 3. A fent leírt módon az E(K) elliptikus görbén zárt lesz. Eddigi
leges testb®l való, amelynek karakterisztikája nem de niálva az
összeadás m¶velete észrevételeinket az úgynevezett
csoport törvényben
foglalhatjuk össze:
98
FEJEZET 10.
10.2. de níció.
Legyen
E(K)
egy
ELLIPTIKUS GÖRBÉK
K (Char(K) ∈ / {2, 3})
test feletti, az
y 2 = x3 + ax + b P = (x1 , y1 ), Q = (x2 , y2 ) P + Q = (x3 , y3 ) pont koordinátáit a
egyenlettel de niált elliptikus görbe. Legyen továbbá
E(K)-beli
O
nem
pontok. Ekkor a
következ®képpen adjuk meg: (1) Ha
x1 6= x2 ,
akkor
x3 = α2 − x1 − x2 ,
(2) Ha
x1 = x2
és
y1 6= y2 ,
és
y3 = α(x1 − x3 ) − y1 ,
ahol
α=
y2 − y1 . x2 − x1
akkor
P + Q = O.
(3) Ha
P =Q
és
y1 6= 0,
x3 = α2 − 2x1 ,
(4) Ha
P =Q
és
y1 = 0,
akkor
és
y3 = α(x1 − x3 ) − y1 ,
ahol
α=
3x21 + a . 2y1
akkor
P + Q = O.
Továbbá minden
P ∈ E(K)
esetén legyen
P + O = P. Tulajdonképpen készen is állunk arra, hogy elliptikus görbék segítségével egy kommutatív csoportot de niáljunk.
10.3. tétel. értelmezett
A fenti jelöléseket és eljárást használva,
+
E(K)
elliptikus görbén
m¶velet rendelkezik a következ® tulajdonságokkal:
10.1. ALAPGONDOLATOK
(i)
P +Q=Q+P P +O =O
(ii)
(iii) minden
minden
minden
P ∈ E(K)
99
P, Q ∈ E(K)
P ∈ E(K)
esetén (kommutativitás),
esetén (egységelem létezése),
esetén található
−P ∈ E(K),
amelyre
P + (−P ) = O
(inverz létezése), (iv) minden
P, Q, R ∈ E(K) esetén P +(Q+R) = (P +Q)+R
Más szavakkal, és a
O
E(K)
(asszociativitás).
pontjainak a halmaza abel csoportot alkot az
+
m¶velettel
egységelemmel.
A tétel teljes bizonyítását mell®zzük, mivel az asszociativitás belátása komplikált. A többi tulajdonság viszont rögtön adódik. A kommutativitás következik egyrészt a formulák de níciójából, másrészt abból a tényb®l, hogy a átmen® egyenes megegyezik a
Q, P
P, Q ponton
ponton átmen®vel. Az egységelem létezése a
de nícióból következik, míg tetsz®leges
P
pont inverze, sajátmaga
x-tengelyre
vett tükörképe lesz.
10.1.2.
Projektív koordináták 2
A közönséges euklidészi sík (R ) pontjait szokásos módon valós számpárokkal adjuk meg. Ezeket a n koordinátáknak nevezzük. Sokszor azonban szükségünk van az úgynevezett
projektív koordináták
használatára.
Tekintsük az
{(x, y, z) | x, y, z ∈ R} \ (0, 0, 0) (x1 , y1 , z1 ) és (x2 , y2 , z2 ) elemek akkor tartoznak egy osztályba, ha létezik olyan c ∈ R, amelyre számhármasok halmazát. Osztályozzuk a halmaz elemeit: az
x1 = cx2 , y1 = cy2 , z1 = cz2 . (x1 , y1 , z1 ) ekvivalenciaosztályát Ha z 6= 0, akkor
jelölje
(x, y, z) ∼
(x : y : z). x y , ,1 . z z
100
FEJEZET 10.
ELLIPTIKUS GÖRBÉK
x y x y z , z , 1 -t, amely megegyezik a z , z a n koordinátájú ponttal, a projektív sík egy nevezzük. Ha z = 0, akkor az (x : y : 0) pontokat
véges pontjának végtelen pontnak hívjuk. Tekintsük most az
R3
euklidészi teret. Vegyünk egy derékszög¶ koordináta-
rendszert és vizsgáljuk az origón átmen® összes egyenes halmazát. Jelöljük ezt a
e ∈ P 2 nem fekszik a z = 0 síkban, akkor egyetlen Q(e) pontban metszi a z = 1 egyenlettel meghatározott síkot. Ha Q(e) koordinátái (x∗ , y ∗ , 1), akkor e a (cx∗ , cy ∗ , c) c ∈ R pontokból áll. Tekintsünk egy f egyenest, amely a z = 0 síkon fekszik és nem azonos az x-tengellyel. Ekkor f -nek van olyan x0 , y 0a n koordinátájú pontja, amelyre x0 0 y 6= 0. Ekkor f pontjainak koordinátái c y0 , c c ∈ R. Ha f azonos az xhalmazt
P 2 -vel.
Ha az
f
tengellyel, akkor Vizsgáljuk
P
2
pontjainak koordinátái
(c, 0).
végtelen pontjait. Azt szoktuk mondani, hogy két párhuza-
mos egyenes a végtelenben metszi egymást. Legyen tehát két nem függ®leges párhuzamos egyenes
y = mx + b1 ahol
b1 6= b2 ,
és
y = mx + b2 ,
és
y = mx + b2 z.
homogén formában:
y = mx + b1 z
Az egyenletrendszert megoldva azt kapjuk, hogy
z=0
és
y = mx.
Mivel a három változó nem lehet egyszerre
0,
ezért
x 6= 0-val
oszthatunk, így
kapjuk, hogy az
(x : mx : 0) = (1 : m : 0) pontban lesz a metszéspont. Függ®leges egyenesek esetén, ha akkor
(0 : 1 : 0)-t
x = c1
és
x = c2 ,
kapunk.
Most térjünk vissza az elliptikus görbénkhez, tehát
E(K) az y 2 = x3 +ax+b
egyenlettel adott. Ekkor a megfelel® homogén forma
y 2 z = x3 + axz 2 + bz 3 . Egy tetsz®leges
E(K)-n
fekv®
(x, y)
(x : y : 1) pontoknak a E(K) melyik pontja fekszik
pont megfelel az
projektív verzióban. Ha meg akarjuk keresni, hogy
10.1. ALAPGONDOLATOK
a végtelenben, tekintsük a
z =0
esetet. Ekkor
x3 = 0-t
x = 0. Így y -nal
kapunk, azaz
y bármilyen nemnulla eelem lehet. (0 : y : 0) = (0 : 1 : 0) hármassal reprezentált maradékosztály az egyetlen végtelen pont E(K)-n. Eredményünk összecseng az eddig tárgyaltakkal, miszerint (0 : 1 : 0) minden függ®leges egyenesen rajta van, tehát minden függ®leges egyenes a (0 : 1 : 0) végtelen pontban metszi E(K)-t. Ezért feleltetjük meg O -nak a (0 : 1 : 0) osztályt. A fenti gondolatmenetet gyakran alkalmazzuk tetsz®leges K test feletti nn dimenziós vektortérben. Jelölje K az (x1 , . . . , xn ) xj ∈ K elemek (pontok) halmazát a koordinátánkénti összeadással és a c(x1 , . . . , xn ) = (cx1 , . . . , cxn ) n skalárszorzással. K n-dimenziós vektortér, elemeit pontoknak (is) szokás ne n n vezni. Azt modjuk, hogy K a K test feletti a n tér . Valamely P ∈ K pont koordinátái legyenek (x1 , . . . , xn ) xj ∈ K . Ezek a P pont a n koorn+1 dinátái. Hogyan adjuk meg P projektív koordinátáit? A K tér elemei az (y1 , . . . , yn , yn+1 ) vektorok. Azt mondjuk, hogy y1 , . . . , yn , yn+1 elemek a P pont
Mivel a
(0 : 0 : 0)
101
kizárt, ezért
oszthatunk és kapjuk, hogy a
projektív koordinátái, ha
y1 yn+1
Az
n-dimenziós
,...,
yn yn+1
,1
= (x1 , . . . , xn ).
n
projektív tér (PK ) fogalmát így vezethetjük be: a
vektortérb®l hagyjuk el a
K n+1
(0, 0, . . . , 0) pontot, és készítsünk egy osztályozást úgy, {z } | n+1 -szer
(x1 , . . . , xn , xn+1 ) és (y1 , . . . , yn , yn+1 ) elemeket soroljuk egy osztályba, ha létezik olyan 0 6= c ∈ K elem, amellyel xj = yj (j = 1, 2, . . . , n + 1). Az n ilymódon létrejött ekvivalenciaosztályokat PK elemeinek (pontjainak) nevezzük. hogy az
Világos, hogy az
(x1 , . . . , xn ) → (x1 , . . . , xn , 1) n K n elemit Pn -be viszi. Vegyük észre, hogy azon PK -beli pontoknak, n n amelyekre xn+1 = 0, nincs K -beli ®se. Ezeket nevezzük PK végtelen (távoli) leképezés
pontjainak.
10.4. de níció.
Egy
K struktúra feletti f polinomot homogén n-edfokú axi y j z k alakú tagokból áll, ahol i + j + k = n.
linomnak nevezzük, ha Ha
f ∈ K[x, y, z]
homogén
n-edfokú
polinom, akkor
f (cx, cy, cz) = cn f (x, y, z)
po-
102
FEJEZET 10.
ELLIPTIKUS GÖRBÉK
c ∈ K elemre. Ekkor az is igaz, hogy ha (x1 , y1 , z1 ) ∼ (x2 , y2 , z2 ), akkor f ((x1 , y1 , z1 )) = 0 akkor és csak akkor teljesül, ha f (x2 , y2 , z2 ) = 0. Tehát pél2 dául PK -ben f gyökei jól de niáltak, hiszen nem függnek az ekvivalenciaosztály
minden
reprezentánsától. Ez egy fontos tulajdonsága a homogén polinomiknak, mivel ez tetsz®leges polinom esetén nem teljesül. Például, ha
f (x, y, z) = x2 + 2y − 3z, akkor
(1, 1, 1)
gyök, viszont a vele ekvivalens
(2, 2, 2)
nem. Tehát tetsz®leges
polinom esetén a gyökök függnek a reprezentánstól. A
kétváltozós
f (x, y)
polinomot
a
z
változó
megfelel®
hatványának
beillesztésével tehetjük homogénné. Például, ha
F (x, y) = y 2 − x3 − ax − b, akkor
f (x, y, z) = y 2 z − x3 − axz 2 − bz 3 homogén harmadfokú polinom lesz, és igaz, hogy
f (x, y, z) = z n f
x y , , z z
továbbá
F (x, y) = f (x, y, 1).
10.1.3.
Elliptikus görbék (mod n)
Néha szükségünk lehet arra, hogy elliptikus görbékkel számoljunk ahol ®ket
n összetett, vagy Q feletti elliptikus görbéket kell vennünk és (mod n), ahol n tesz®leges egész. A probléma ott van, hogy
(mod n), redukálni ekkor tu-
lajdonképpen nem testben számolunk, hanem csak egységelemes kommutatív gy¶r¶ben. Tudjuk például, hogy den ideálja f®ideál, amelyek akkor
Z/nZ
nZ
Z
egységelemes integritási tartomány és min-
alakúak, ahol
n ∈ N.
Ha
nZ
maximális ideál,
test, különben lehet, hogy még csak nem is integritási tartomány,
hiszen ez csak akkor teljesül, ha
nZ
prímideál.
Tehát adódik a kérdés, hogy érdemes-e er®ltetni a Z/nZ feletti számolást. A válasz az, hogy prímfaktorizációnál éppen azt a tényt használjuk ki, hogy a
10.2. TORZIÓS PONTOK
103
szorzás nem invertálható, azaz van amikor nem tudunk osztani. Ezért hasznos lehet megfontolni a következ®ket. Ha
n, 4a3 + 27b2 = 1, (mod p)
redukálva az elliptikus görbét, szin-
tén elliptikus görbét kapunk, továbbá ha
Z/nZ felett el tudunk végezni egy (mod p) redukálva az eredményt,
akkor
n
minden
p
összeadást, akkor
prímosztójára
n
p
minden
prímosztójára
ugyanazt kapjuk, mintha el®bb a redukálást végeztük volna el, utána a m¶vele-
(mod p).
tet
10.5. tétel. egy
E Zn1 n2
A
O
szimbólum redukálva sajátmaga.
Legyen
n1 , n2
páratlan egész és
(n1 , n2 ) = 1,
továbbá tekintsünk
feletti elliptikus görbét. Ekkor létezik olyan csoportizomor zmus,
amellyel
E(Zn1 n2 ) ∼ = E(Zn1 ) × E(Zn2 ).
10.2.
Torziós pontok
Az úgynevezett
torziós pontok központi szerepet játszanak az elliptikus görbék
elméletében. A véges rend¶ pontokat nevezzük így. Legyen
E(K) egy, a K
test feletti elliptikus görbe, és vezessük be a következ®
jelölést
E[n] := P ∈ E K | nP = O . Azt is mondhatjuk, hogy tartalmaz
K -beli
K
a
K
koordinátájú pontokat is, nem csak
Például tekintsünk egy nem rozása könny¶
algebrai lezártja. Hangsúlyozzuk, hogy
y 2 = x3 + ax + b
2
K -belieket. E[2]
karakterisztikájú testet. Ekkor
E[n]
meghatá-
alapján. Legyen
y 2 = (x − e1 )(x − e2 )(x − e3 ), ahol
e1 , e2 , e3 ∈ K .
P -beli
Egy
P
pontra
2P = O
akkor és csak akkor teljesül, ha a
érint® függ®leges. Ez azt jelenti, hogy az
y
koordináta minden esetben
Tehát kapjuk, hogy
E[2] := {O, (e1 , 0), (e2 , 0), (e3 , 0)} , amely izomorf
Z2 × Z2 -vel.
0.
104
FEJEZET 10.
Ha a
K
test karakterisztikája
2,
ELLIPTIKUS GÖRBÉK
akkor a helyzet bonyolultabb, de rövid
számolással megoldható. Két esetet kapunk, ahol az egyiknél az
√ E[2] := {O, (0, a6 )} eredményre jutunk, ahol a görbe de niálására az
y 2 + xy + x3 + a2 x2 + a6 = 0 (a6 6= 0) egyenletet használjuk. A másik esetben
E[2] := {O} , ahol
y 2 + a3 y + x3 + a4 x + a6 = 0 (a3 6= 0). Észrevételeinket a következ® segédtételben foglaljuk össze:
10.6. lemma. Char(K) 6= 2,
Legyen
E(K)
egy,
a
K
test
feletti
elliptikus
görbe.
Ha
akkor
E[2] ∼ = Z2 × Z2 , ha
Char(K) = 2,
akkor
E[2] ∼ =0
vagy
E[2] ∼ = Z2 .
Az állítás általánosítható:
10.7. tétel. Ha
Legyen
Char(K) - n,
E(K) egy, a K test feletti elliptikus görbe és n pozitív egész. Char(K) = 0, akkor
vagy
E[n] ∼ = Zn × Zn . Ha
Char(K) = p > 0
és
p | n,
akkor legyen
E[n] ∼ = Zn0 × Zn0
vagy
n = pr n0 ,
ahol
p - n0 .
E[2] ∼ = Zn × Zn0 .
Ekkor
10.3. ELLIPTIKUS GÖRBÉK VÉGES TEST FELETT
10.3.
105
Elliptikus görbék véges test felett
Mint ahogy azt a fejezet elején említettük, számunkra legfontosabbak a véges testek fölött de niált elliptikus görbék. Kiemelend® azon hogy végesrend¶ek és adható olyan intervallum
Fp (p
jó tulajdonságuk, prím) esetén, amelyben
véletlenszer¶en választott görbék rendje eléggé egyenletesen oszlik el. Ez a tulajdonság teszi a véges testek feletti elliptikus görbéket prímfaktorizációra alkalmasnak. a Az els® állításunkhoz szükség van egy, az algebrában jól ismert, csoportelméleti tételre:
10.8. tétel.
Egy
G
véges Abel csoport izomorf a
Zn1 × Zn2 × · · · × Znr csoporttal, ahol
ni | ni+1
minden
i = 1, 2, . . . , r − 1
esetén. Az
ni
számok egyér-
telm¶en adottak.
10.9. tétel.
Legyen
E(Fq )
az
Fq
E(Fq ) ∼ = Zn ahol
n≥1
egész, vagy
n1 | n2
véges test feletti elliptikus görbe. Ekkor vagy
E(Fq ) ∼ = Zn1 × Zn2 ,
egészek.
(10.8) tételb®l kapjuk, hogy minden Zni csoportban van n1 elem, n1 -nek, tehát E(Fq )-ban van legalább nr1 elem amelynek rendja osztja n1 -et. A (10.7) tétel viszont azt implikálja, hogy legfel2 jebb n1 ilyen pont van. Tehát kaptuk, hogy r ≤ 2, amivel a tételt igazoltuk.
Bizonyítás: A
amelynek rendje biztosan osztója
Mit tudunk mondani véges test feletti elliptikus görbék rendjér®l? Ezzel a kérdéssel foglalkozik a következ® állítás:
10.10. tétel (Hasse). Ekkor az
E(Fq )
E(Fq ) az Fq véges ](E(Fq )) számára
Legyen
pontjainak
test feletti elliptikus görbe.
√ |](E(Fq )) − (q − 1)| < 2 q. Segítségül a fenti gondolatmenet tanulmányozásához, tekintsük a következ® példát.
106
FEJEZET 10.
10.11. példa.
Legyen
E
y 2 = x3 + 2
az
ELLIPTIKUS GÖRBÉK
egyenlettel adott
F7
feletti
elliptikus görbe. Ekkor
E(F7 ) = {O, (0, 3), (0, 4), (3, 1), (3, 6), (5, 1), (5, 6), (6, 1), (6, 6)} . Könnyen kiszámolhatjuk, hogy minden
0.
Ugyanez nem áll fenn a nem
O
P ∈ E(F7 ) pontra igaz, hogy 3P = 3-nál kisebb számokra, tehát
elemekre
E(F7 ) ∼ = Z3 × Z3 .
További jellemzést ad
E(Fq )-ról
a következ® két tétel.
......................................................
10.4.
Prímtfaktorizáció elliptikus görbékkel
H.W. Lenstra hatékony algoritmust dolgozott ki egész számok prímtényez®s fel-
60 de200 bináris számjegynek felel meg) számok fak-
bontására (prímfelbontásra). Ez az algoritmus a gyakorlatban körülbelül cimális számjegy¶ (ez körülbelül
torizációjára is alkalmas. Mivel ez az algoritmus leghatékonyabban a (20 és
30
nagyobb
számjegy közti) prímfaktorokat találja meg, ezért célszer¶ egy má-
sik faktorizáló algoritmussal együtt alkalmazni, amely gyorsabban megtalálja a kisebb prímtényez®ket. Miel®tt Lenstra algoritmusának tárgyalására rétérnénk, ismertetünk egy érdekes példát, illetve egy algoritmust.
10.12. példa.
Vegyük a
4453 = 61 · 73
y 2 = x3 + 10x − 2
összetett számot és az
E,
(mod 4453)
kongruenciával de niált elliptikus görbét. Tekintsük a következ® számolást: próbáljuk megadni
2P -t.
A
P
3P
értékét, ha
P = (1, 3).
El®ször is kiszámoljuk
pontba húzott érint® iránytangense
3x2 + 10 13 = ≡ 3713 2y 6
(mod 4453).
10.4. PRÍMTFAKTORIZÁCIÓ ELLIPTIKUS GÖRBÉKKEL
Kihasználtuk a tényt, hogy
(6, 4453) = 1,
107
így meg tudtuk határozni
6
inverzét:
6−1 ≡ 3711
(mod 4453).
Ekkor már könnyen kiszámolhatjuk a
2P = (x, y)
pont koordinátáit:
x ≡ 37132 − 2 ≡ 4332, y ≡ −3713(x − 1) − 3 ≡ 3230. Most a
3P = 2P + P
ponthoz húzott érint® egyenes meredekségének ki-
számolása következik:
3230 − 3 3227 = . 4332 − 1 4331
D = (4331, 4453) = 61 6= 1, ezért nem tudjuk meghatározni 4331 (mod 4453). Itt elakadtunk a számolással, egyúttal megtaláltuk 4453-nak az egyi faktorát, nevezetesen D = 61-et. Mivel
inverzét
Emlékeztetünk rá, hogy
E(Z4453 ) = E(Z61 ) × E(Z73 ). Tekintsük a következ® sorozatokat:
P ≡ (1, 3), 2P ≡ (1, 58), 3P ≡ O, 4P ≡ (1, 3), . . .
(mod 61),
és
P ≡ (1, 3), 2P ≡ (25, 18), 3P ≡ (28, 44), . . . , 64P ≡ O, . . . A faktorizálás
alapötlete
innen származik. Ha
(mod 73).
egy szám
többszöröseit
számolgatjuk folyamatosan (mod n) és eljutunk egy olyan pontra, ahol nem tudunk tovább számolni, ahogy a fenti példában láttuk, akkor jó esélyünk van, hogy megtaláltuk
n
egy faktorát. Persze adódhatott volna olyan szituáció az
el®bbi példában, hogy
3P = O-t
kapunk
(mod 73)
esetén is. Ekkor
D = 4453,
azaz triviális faktort találtunk. Utóbbi esetre szerencsére kicsi az esély. Most ismerkedjünk meg a
Pollard-féle p−1 algoritmussal , amely Lenstra
algoritmusának is az alapját képezi.
10.13. de níció. mint
K + 1.
Az
m∈N
szám
K − sima,
ha minden prímfaktora kisebb,
108
FEJEZET 10.
Tegyük fel, hogy véletlen
a ∈ Z
n = pq
p, q
összetett egész, ahol
K
számot és egy megfelel®
kintjük megfelel®nek, ha
p − 1 K − sima
ELLIPTIKUS GÖRBÉK
prímek. Válasszunk egy
természetes számot.
K -t
akkor te-
és alkalmazható rá, a kis Fermat tétel,
azaz
ap−1 ≡ aK! ≡ 1
(mod p).
(10.1)
K! tartalmaz minden prímtényez®t K -ig, ezért valószín¶, hogy p − 1 osztója lesz K!-nak. Azért csak valószín¶, mert van olyan ritka kivétel, például amikor p − 1 többszöröse egy K/2 és K közti prím négyzetének, amikor ez nem áll fenn. Továbbá a kis Fermat tétel sem áll fenn, ha p | a. Hangsúlyozzuk, hogy Mivel
ezen gátló tényez®k fennállásának az esélye igen csekély. Tehát legyen
k = K!
és végezzük el a következ® számolást:
D = ak
(mod n) − 1, n .
p | D. Megjegyezzük, hatványozás módszerével, (ak (mod n), n) pedig
(10.1)
sal
miatt világos, hogy
a gyorseuklidészi algoritmus-
hogy az
ak (mod n)
hatékonyan kiszámítható. Tehát kaptuk, hogy megfelel®
nak, viszont ha kiderül, hogy hiszen ekkor
D=n
q
K
választás esetén
is osztója
D-nek,
D
faktora lesz az
n
szám-
akkor nem értünk el semmit,
triviális faktort kaptunk.
Vizsgáljuk most ezt a kérdést, ehhez tegyük fel, hogy q − 1 osztható egy t > K prímmel. A Z∗q ciklikus multiplikatív csoport elemei között legfeljebb (q − 1)/t darab rendje nem osztható t-vel, és legalább (t − 1)(q − 1)/t rendje 2 osztható t-vel. Ezek az értékek egyébként pontosak, ha t - q − 1. Tehát nagy a valószín¶sége, hogy a rendje osztható t-vel. Ekkor
aK! 6≡ 1 Tehát kaptuk, hogy ha
D = ak Mi történik, ha lában
D = n-et
aK! − 1
(mod q).
többszöröse
(mod n) − 1, n = ak
q − 1-nek
p-nek,
de
q -nak
nem, akkor
(mod n) − 1, pq = p.
egyik prímfaktora sem nagyobb, mint
K?
Ekkor álta-
kapunk, azaz triviális faktort. Próbálkozhatunk újra kisebb
értékkel, ügyelve arra, hogy egyik f® problémája
K
p − 1,
vagy
q − 1 K -sima legyen. A p − 1 K túl kicsi, akkor csökken
megválasztása. Ha
K
módszer az esély,
10.4. PRÍMTFAKTORIZÁCIÓ ELLIPTIKUS GÖRBÉKKEL
hogy
p − 1,
q − 1 K -sima
vagy
109
legyen, ha túl nagy, akkor lassú lesz a számolás.
A gyakorlat azt mutatja, hogy a módszer egy
108
körüli
K
értékkel jól m¶ködik.
Tulajdonképpen akkor is van esély, hogy nem triviális faktort kapunk, ha és
q−1
prímfaktorai kb.
20
mint azt a következ® gondolatmenet mutatja. Tegyük fel, hogy egy
aK!
p−1
decimális számjegy¶ek, de ez az esély igen csekély,
t > K prímosztója. Ekkor ≡ 1 (mod p)-t kapjunk:
p − 1-nek
van
az el®z® számolás alapján az esély arra, hogy
1 1 ∼ 20 . t 10 Az elliptikus görbés faktorizáció ugyanerre az elvre épül, viszont ez az esély megnövelhet®
p−1 algoritmust. A program bemeneti értéke (x, y) x és y legnagyobb közös oszakkor az algoritmus n egy nem triviális faktorával
Most ismertetjük a Pollard-féle
n≥2
összetett egész szám. Természetesen
tóját jelenti. Ha
n
összetett,
tér vissza.
Pollard-pmínuszegy(n) 1 2 3 4 5 6 7 8 9 10 11 12
k ← K! a ← Random(2, n − 1) D ← (a, n) if D > 1 then return D D ← (ak − 1, n) if 1 < D < n then return D if D = 1 then K ← K + 1
goto 1 else goto 2
Miel®tt Lenstra algoritmusára rátérnénk, bizonyos el®készületeket teszünk.
x1 = a1 /n1 , x2 = a2 /n2 redukált alakban felírt racionális (n1 , m) = (n2 , m) = 1. Az x1 − x2 redukált alakja legyen x1 − x2 = a/n. Ekkor nyilvánvalóan (n, m) = 1, mivel n | [n1 , n2 ]. Az x1 és x2 racionális számokat kongruenseknek mondjuk (mod m), jelben x1 ≡ x2 Legyen
m
egész,
számok, amelyekre
110
FEJEZET 10.
(mod m),
ha
ELLIPTIKUS GÖRBÉK
m | a.
Könnyen beláthatjuk, hogy e kongruencia reláció ekvivalencia reláció az
na n
o | a ∈ Z, n ∈ N, (a, n) = 1, (n, m) = 1
a/n-hez található olyan b ∈ {0, 1, . . . , m − 1} egész, amellyel a/n ≡ b (mod m). Ez nyilvánvaló, mivel az a ≡ xn (mod m) kongruencia (n, m) = 1 miatt megoldható. 2 3 Legyen E : y = x + ax + b adott elliptikus görbe, ahol x, y ∈ Z. Tegyük fel, hogy P = (x, y) racionális pont a görbén. Ekkor P (mod n) alatt az (x (mod n), y (mod n)) párt értjük. Az algoritmus során hatékonyan ki kell számítanunk a kP (mod n) értékeket. Erre hatékony eljárás lehet az úgynevezett duplázás módszere Pj+1 = 2Pj P0 = P (Pj = 2j P ), . . . , ahol j = 0, 1, 2, . . . . E(Q) pontjait és ezek összegét mindig (mod n) tekintjük. Akkor helyes a számolás, ha a számítások során el®forduló valamennyi nevez® relatív prím n-
gy¶r¶ben. Továbbá
hez.
10.14. tétel.
Legyen
E : y 2 = x3 + ax + b, (a, b ∈ Z) elliptikus görbe,
P1 , P2
(4a3 + 27b2 , n) = 1.
Legyen
pontok koordinátáinak nevez®i az
E
n-hez
P1 , P2 ∈ E(Q) P1 6= −P2 ,
és a
relatív prímek. Legyen továbbá
(mod p) : y 2 = x3 + ax + b,
a, b ∈ Fp , a ≡ a (mod p), b ≡ b (mod p). P1 + P2 ∈ E(Q) pont (racionális) koordinátáiban prímek n-hez, kivéve, ha van olyan p | n prímszám, amelyre ahol
Ekkor a
P1 az
E (mod p)
Bizonyítás:
(mod p) + P2
a nevez®k relatív
(mod p) = O,
görbén.
Tegyük fel, hogy a
P1 = (x1 , y1 ), P2 = (x2 , y2 ), P1 + P2 ∈ E(Q) n-hez relatív prímek. Legyen p | n. Meg kell
pontok koordinátáiban a nevez®k mutatni, hogy
P1
(mod p) + P2
(mod p) 6= O
(mod p).
10.4. PRÍMTFAKTORIZÁCIÓ ELLIPTIKUS GÖRBÉKKEL
x1 ≡ x2 (mod p), akkor az E (mod p) görbén vett összeadási P1 (mod p) + P2 (mod p) nem a végtelen távoli pont. Tegyük fel, hogy x1 ≡ x2 (mod p). Legyen el®ször P1 = P2 . Ha
2P1
(mod p) = (x3
(mod p), y3
ahol
x3 =
3x21 + a 2y1
és
y3 = −y1 +
111
törvény miatt
(mod p)),
2 − 2x1
3x21 + a 2y1
· (x1 − x3 ).
Belátjuk, hogy p - 2y1 . Ha ugyanis p | 2y1 , akkor amiatt, hogy x3 nevez®jének p nem osztója, ezért 3x21 +a számlálója p többszöröse lenne. De ekkor x1 az x3 + ax + b ∈ E (mod p) polinomnak gyöke, továbbá x1 gyöke a 3x2 + a polinomnak 3 is. Tehát x + ax + b ∈ E(Fp )-nek van többszörös gyöke, ezért diszkriminánsa
4a3 + 27b ≡ 0
(mod p),
ami ellentmond feltételünknek.
x1 ≡ x2 (mod p), x1 6= x2 , ezért x2 = x1 + p x, r ≥ 1, és x számlálója is, nevez®je is relatív prím n-hez. Mivel feltevésünk szerint P1 + P2 koordinátáinak nevez®i nem oszthatók p-vel, ezért P1 ∗ P2 = (x3 , y3 ) pontra az 2 y2 − y1 − (x1 − x2 ) x3 = x2 − x1 Tegyük fel, hogy
P1 6= P2 .
Mivel
r
és
y3 = −y1 +
formulákat alkalmazva adódik, hogy
y2 − y1 x2 − x1
· (x1 − x3 )
y2 = y1 + pr y .
Másrészt
y22
=
(x1 + pr x)3 + a(x1 + pr x) + b =
= x31 + ax1 + b + pr x(3x21 + a) = = y12 + pr x(3x21 + a)
(mod pr+1 ).
112
FEJEZET 10.
Mivel
x1 ≡ x2 (mod p), y1 ≡ y2 (mod p), P1
(mod p) + P2
ezért
ELLIPTIKUS GÖRBÉK
P1 ≡ P2 (mod p),
(mod p) = 2P1
és
(mod p),
O (mod p) , ha y1 = y2 ≡ 0 (mod p). pr+1 | y22 − y12 , és így pr+1 | 3x21 + a, és így 3x21 + a ≡ 0 x3 + ax + b polinomnak van többszörös gyöke. Tehát
és ez akkor és csak akkor Ha ez teljesül, akkor
(mod p),
azaz az
P1
(mod p) + P2
(mod p) 6= O
(mod p).
p | n-re P1 (mod p) + P2 (mod p) 6= O (mod p). meg kell mutatni, hogy P1 + P2 -ben a koordináták nevez®i relatív prímek n-hez, azaz nem oszthatók p-vel, minden p | n-re. Legyen p | n. Ha x2 6≡ x1 (mod p), akkor az összegzési képletb®l világos, hogy P1 + P2 koordinátáiban a nevez®k relatív prímek n-hez. Tegyük fel, hogy x2 ≡ x1 (mod p). Ekkor y2 ≡ ±y1 (mod p), és P1 (mod p) + P2 (mod p) 6= O (mod p) miatt y2 ≡ y1 (mod p), továbbá y2 6≡ 0 (mod p). Ha P1 = P2 , akkor a 2P1 formulára vonatkozó képletb®l rögtön adódik, hogy 2P1 -ben a nevez®k relatív prímek p-hez. r Ha P1 6= P2 , x2 = x1 + p x, x relatív prím p-hez. Az összegzési formulából Fordítva, tegyük fel, hogy minden
kapjuk, hogy
y22 − y12 ≡ 3x21 + a (mod p). x2 − x1 Mivel
p - y2 + y1 = 2y1 (mod p),
ezért relatív prím az
y2 − y1 y22 − y12 = (y2 + y1 )(x2 − x1 ) x2 − x1 nevez®jéhez, és így az összegzési formulával az állítás adódik. Könny¶ belátni, hogy ha P = (x, y), racionális pont az E görbén, akkor x = p/e2 , y = q/e3 , (p, e) = (q, e) = 1. Legyen ugyanis x = u/M , y = v/N , ahol M, N ≥ 1, és (u, M ) = (v, N ) = 1. Ekkor
v2 u3 u2 u = + a · +b· + c, N2 M3 M2 M és így
M 3 v 2 = N 2 u3 + aN 2 M u2 + bN 2 M 2 u + cN 2 M 2 ,
(10.2)
10.4. PRÍMTFAKTORIZÁCIÓ ELLIPTIKUS GÖRBÉKKEL
113
N 2 | M 3 v 2 , N 2 | M 3 . Belátjuk, hogy M 3 | N 2 . Nyilvánvaló, hogy M | N u , és (u, M )=1 miatt M | N 2 . Ezért M 2 | N 2 u2 , így M | N . Még egyszer 3 2 3 3 2 3 2 megvizsgálva a (10.2) egyenletet, M | N u , M | N adódik, tehát M = N . ezért
2 2
Ezek után ismertetjük
Lenstra elliptikus görbe algoritmusát, amelynek
n ≥ 3 összetett egész szám, és (n, 6) = 1, kimenete pedig nnek egy nemtriviális D osztója. Megjegyezzük még, hogy x1 , y1 jelöli tetsz®leges P ∈ E(Q) pont koordinátáit, ahol E : y 2 = x3 + ax + b elliptikus görbe. Ahogy 2 3 az el®z®ekben láthattuk, megfelel® d, p, q értékekkel x1 = p/d , y1 = q/d írható. Feltesszük, hogy a Koordnev(P ) függvény a d értékkel tér vissza.
bemenete egy
Elliptikus-Lenstra(n) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
a ← Random(1, n) x1 ← Random(1, n) y1 ← Random(1, n) b ← y12 − x31 − ax1 (mod n) D ← (4a3 + 27b2 , n) if 1 < D < n then return D if D = n
then goto
1
k ← K! d ← Koordnev(k · P ) D ← (d, n) if 1 < D < n then return D if D = 1 then K ← K + 1
goto 10 else return sikertelen
Kihangsúlyozzuk, hogy vannak olyan implementációk, amelyekben nem használnak, hanem egyéb módon választanak képpen mindegy, ha
k
nagy
kitev®t
a-nak.
K!-t
Ez tulajdon-
megfelel a fentebb taglalt feltételeknek.
Végezetül választ adunk arra a kérdésre, amely sokak fejében felvet®dhet, miszerint miért m¶ködik az elliptikus görbés prímteszt, mikor els® ránézésre
114
FEJEZET 10.
ELLIPTIKUS GÖRBÉK
p − 1 módszerhez képest. Válasszunk tehát véletlenszer¶en egy E elliptikus görbét (mod n). Ha n = pq , valamely p, q prímekre, akkor vizsgáljuk E -t mint egy elliptikus görbét (mod p) és mint egyet (mod q). A Hasse tételb®l tudjuk, hogy csak jól elbonyolítottuk a számolásokat a
√ |](E(Fp )) − (p − 1)| < 2 p. √ √ K -t megfelel®en választottuk, akkor a (p + 1 − 2 p, p + 1 + 2 p) intervallumban a K -sima számok s¶r¶sége elég nagy lesz, továbbá itt a véletlenszer¶en Ha
válsztott elliptikus görbék rendje közel egyenletesen fog eloszlani. Tehát, ha több elliptikus görbét választunk véletlenszer¶en, akkor valamelyik rendje jó eséllyel
K -sima
lesz. Legyen az egyik ilyen
jó eséllyel várhatjuk, hogy ha
P
E.
A fenti megfontolásokat gyelembevéve
egy pont
E -n,
akkor
K!P = O
(mod p),
K!P 6= O
(mod q).
de
Ez pedig azt jelenti, hogy amikor a
K!P (mod n)
pont koordinátáit számoljuk,
p-vel, de q -val nem. n-nek a legnagyobb közös osztójaként kapjuk a számunkra eddig a pillanatig ismeretlen p faktort. Összegezve, a különbség az a p − 1 módszer és az elliptikus között, hogy el®bbinél van ugyan esély, hogy p − 1 K -sima, de ha nem az, akkor nincs mit az érint® egyenes iránytangensének nevez®je osztható lesz Ennek a nevez®nek és
tenni, utóbbinál több görbét is kipróbálhatunk, növelve az esélyét annak, hogy
]E(Fp ) K -sima
10.5.
legyen.
Prímtesztelés elliptikus görbékkel
Az elliptikus görbék elméletére alapozva az elmúlt évtizedekben a gyakorlati életben talán legjobban használható prímtesztel® algoritmusokat fejlesztettek. A faktorizáció esetében egy meglév® módszerre építette Lenstra az elliptikus görbés algoritmusát. Prímtesztelés esetében is hasonló a helyzet, bár itt két lépccs®ben jutunk el az elliptikus görbés prímtesztig, amelyet az angol meg felel®jéb®l -nek (Elliptic Curve Primality Proving) is szokás nevezni.
ECPP
A következ® tétel
Lucas-tesztként
ismert.
10.5. PRÍMTESZTELÉS ELLIPTIKUS GÖRBÉKKEL
10.15. tétel. amire
Az
1
n∈N
115
szám akkor és csak akkor prím, ha létezik olyan
g ∈ N,
és
g n−1 ≡ 1 p
továbbá minden olyan
prímre, amelyre
g
n−1 p
6≡ 1
(mod n), p | n − 1,
fennáll a
(mod n).
kongruencia.
Bizonyítás: Tegyük fel, hogy azaz létezik benne
g
n
prím. Ekkor
Zn
Z∗n
test, tehát
primitív elem, melynek rendje
n − 1.
ciklikus csoport,
Ekkor nyilvánvalóan
teljesül
g Most tegyük fel, hogy
n−1 p
6≡ 1
(mod n).
1 < g < n, g n−1 ≡ 1 (mod n) g
n−1 p
6≡ 1
és
(mod n)
g ∈ Z∗n és a {g, g 2 , . . . , g n−1 } ⊆ Z∗n ∗ elemek mind különböz®ek, azaz n − 1 ≤ |Zn | = ϕ(n), és így ϕ(n) = n − 1. n−1 Ez pontosan azt jelenti, hogy n prím. ≡ 1 Tehát észrevehetjük, hogy a (mod n) fennáll minden (a, n) = 1 választás esetén, ha n prím (tulajdonképminden
p | n − 1, p
prím esetén. Ekkor
pen ezt az állítást fogalmazza meg az úgynevezett ha
n
összetett,
tételre alapozott
kis Fermat-tétel ). Viszont
megbukik a teszten, ezért mondhatjuk, hogy a Lucas-teszt
Lucas-prímteszt determinisztikus prímteszt, amelynek ismertetésénél Faktor(x, i) az x pozitív egész i-edik prímosztóját adja, azaz, ha k x = p1α1 . . . pα k , akkor pi -t (1 ≤ i ≤ k ), továbbá Numfaktor(x) a prímosztók számát jelenti, esetünkben
k -t.
a szám létezik, ezért megK -val jelöljük azt a korlátot, kívánt a értéket. A programban
Mivel sok megfelel®
keresése a gyakorlatban nem jelent problémát, itt amelynél legkés®bb megtalálja az algoritmus a a rossz változó mutatja, hogy ha az
a
érték nem megfelel®.
116
FEJEZET 10.
ELLIPTIKUS GÖRBÉK
Lucas-prímteszt(n, m) 1 2 3 4 5 6 7 8 9 10
a←1 rossz ← hamis if a(n−1) 6≡ 1 (mod n) then a ← a + 1
goto 3 for i ← 1 to Numfaktor(n − 1) if a(n−1)/Faktor(n−1,i) ≡ 1 (mod n) then rossz ← igaz a>K
if
rossz
11 12 13 14
a←a+1
if
15 16
then if rossz then return összetett else return prím then goto 2 else return prím
Ennek a módszernek a f® problémája az, hogy m¶ködéséhez szükségünk van
n−1
faktorizációjára, ami nagyon megnöveli a m¶veletigényt. Éppen ezért a
Lucas-tesztet csak olyan speciális
1
n
számok esetén célszer¶ használni, ahol
n−
prímtényez®s felbontását könny¶ elvégezni. Ilyen speciális számok például a
Fermat-számok, amelyek a 2k + 1 alakú számok.
Lucas módszerét Pocklington és Lehmer is továbbfejlesztették. El®bbi célja az volt, hogy a Lucas teszt akkor is m¶ködjön, ha nem ismerjük prímfaktorizációját. Utóbbi olyan algoritmust, amelyek függhetnek
a
n−1
teljes
alapok keresésével remélte gyorsítani az
p-t®l.
A matematika történelme a következ®
állítás elliptikus görbés változatát tartja úgy számon, mint ECPP.
10.16. tétel (Pockilngton-Lehmer prímteszt ). √ rs (n, s ∈ Z)
és
r≥
n.
Tegyük fel, hogy minden
egész, amelyre fennáll, hogy
aqn−1 ≡ 1
(mod n)
Legyen
q|r
n > 1 egész, n−1 = aq
prímhez létezik olyan
10.5. PRÍMTESZTELÉS ELLIPTIKUS GÖRBÉKKEL
és
Ekkor
n
a(n−1)/q − 1, n = 1. q
prím.
Bizonyítás:
q -nak,
117
Legyen
amelyre
e
q |r,
p
egy prímtényez®je
továbbá
b≡
n-nek és q e a legmagasabb (mod p). Ekkor
(n−1)/q e aq
e
bq ≡ a(n−1) ≡1 q
hatványa
(mod p),
és
bq mivel
e
−1
≡ a(n−1)/q 6≡ 1 q
Kaptuk, hogy
b
rendje
prímtényez®jére, ezért
(mod p),
a(n−1)/q − 1, n = 1. q
(mod p) q e , tehát q e |p − 1. r|p − 1. Így fennáll a √ p>r≥ n
összefüggés, ami azt jelenti, hogy
n
Mivel ez igaz
r
qe
minden
minden prímfaktora nagyobb, mint
√
n.
Ez
viszont kizárólag a prímszámokra teljesülhet. Tehát ennek a módszernek az el®nye a Lucas teszttel szemben, hogy elég faktotizációjának csak egy részét ismernünk. Ha
n
n
többezer decimális számje-
gy¶, akkor egy részének faktorizációját is általában nehéz megtalálni. Ismét az elliptikus görbék segítenek a bajban.
10.17. tétel.
Legyen
n ∈ N, (6, n) = 1, és En egy Z/nZ feletti elliptikus görbe m, s egészek, és s | m. Tegyük fel, hogy találunk
pontjainak a halmaza. Legyenek olyan
P ∈ En
pontot, amelyre
m·P =O
(10.3)
m · P 6= O q
(10.4)
és
s
minden
q
prímfaktorára fennáll. Ekkor
|Ep | ≡ 0
n
minden
(mod s).
p
prímosztójára
118
FEJEZET 10.
Továbbá, ha
√ 4
s> akkor
n
n+1
2
ELLIPTIKUS GÖRBÉK
,
prím.
Bizonyítás: Legyen
p
egy prímosztója
n-nek,
Q=
és legyen
Ep -n
m Pp . s
Ekkor
sQ = mPp = (mP )p = O, így
Q
rendje osztja
prímosztóját
s-nek,
s-et,
ahogy azt láttuk az el®bb is. Ha most vesszük egy
q
akkor
ms m s Q= Pp = Pp = q s q q
m P q
6= O, p
mivel a feltétel szerint
m P 6= O. q Tehát Q rendje nem osztója s/q -nak. Mivel q -t tetsz®legesen választottuk, ezért Q rendje pontosan s. Így azt is megkaptuk, hogy |Ep | ≡ 0
(mod s).
Hasse tételéb®l tudjuk, hogy
|Ep | = p + 1 − t,
ahol
t∈Z
és
√ |t| ≤ 2 p.
A tétel feltételeib®l és az eddigi számolásainkból következik, hogy
√ 4
n+1
2
√ √ 2 < s ≤ |Ep | ≤ p + 2 p + 1 = ( p + 1) .
Átrendezve az egyenl®tlenséget, kapjuk, hogy
2 √ √ 2 ( p + 1) > 4 n + 1 , amelyb®l rögtön adódik, hogy
p> Mivel ez azt jelenti, hogy
n
√
n.
minden prímfaktora nagyobb, mint
prím. Tekintsük a következ® feladatot.
√
n,
ezért
n
10.5. PRÍMTESZTELÉS ELLIPTIKUS GÖRBÉKKEL
10.18. példa.
Legyen
n = 907,
és
E
egy elliptikus görbe az
y 2 = x3 + 10x − 2 kongruenciával adott. Legyen továbbá
119
(mod n)
p1 = 71.
Ekkor
2 p1 > 9071/4 + 1 ∼ 42.1.
Ha
907
P = (819, 784),
akkor
71P = O.
A
?? tétel értelmében kapjuk, hogy
prím.
Tehát nincs más dolgunk, mint adott elliptikus görbét
Z/nZ
n
esetén találnunk kell egy alkalmas köze van n faktorizációjához. prím. Láthatjuk, hogy a módszer
felett, amely rendjének
Ez azt jelenti, hogy a görbe rendje
ha
n
f faktorizációját 10.5 példában, mivel tudjuk, hogy prím. A valóságban, f®leg többezer jegy¶ n esetén azonban csak reméljük, hogy n1 prím. Az egzakt bizonyításhoz még n1 prímségét is be kell látni. Ez úgy történik, hogy n1 -re is meghívjuk a prímtesztel® algoritmust, akkor m¶ködik, ha ismerjük. Ha
n1 71
m-et m = f n1
m,
alakba tudjuk írni, ahol
prím akkor jól jártunk, ezt láthattuk a
amely egy rekurzív futást eredményez. Tehát tekintsük az
s = n1
Ekkor megtaláltuk
n1
P pontot a görbén. Kicsi az · P = f · P nincs de niálva. f · P = O, akkor új pontot kell
választást és egy
esélye, de el®fordulhat, hogy azt találjuk, hogy egy valódi osztóját. Ha
m n1
választanunk. Egyébként ellen®rizzük, hogy
n1 · (f · P ) = m · P = O teljesül-e. Ha igen akkor
n1
prím mivolta és
P
létezése bizonyítja, hogy
n
prím.
El®ször egy általános sémát vázolunk fel, amelynél a 10.17. tétel jelöléseit használjuk. A bemeneti érték
n>1
egész szám, amelyre
(6, n) = 1.
120
FEJEZET 10.
ELLIPTIKUS GÖRBÉK
Elliptikus-prímteszt(n) 1 2 3
En ← véletlen (Z/nZ) feletti elliptikus m ← |En | if m = q · s, ahol s valószín¶leg prím
4 5 6
if
7 8 9 10 11 12 13 14 15 16
then goto 8 else goto 1
görbe
és
q
faktorizációja ismert
√ 2 s ≤ ( 4 n + 1)
then goto 1
P ← véletlen pont (En )-b®l if qP nem de niált
if if
then return összetett (m/q) · P = O
then goto 8 m · P 6= O
then return összetett while nem vagyunk biztosak do Elliptikus-prímteszt(s)
A 13. lépésben a nem vagyunk biztosak azt jelenti, hogy ha s értéke túl nagy, akkor túl sok id®t vesz igénybe a prímtesztje. Mivel s folyamatosan csökken minden rekurziós lépésben, minden sikeres utóbb
m = qs
felbontásnál, ezért el®bb-
elég kicsi lesz ahhoz, hogy könnyen ellen®rizzük prím mivoltát. Ezt
például egyszer¶en próbaosztással is megtehetjük.
Goldwasser és Kilian javasolták ezt a gondolatmenetet. Az ® eljárásukban rögzített f értéket használtak, nevezetesen a 2-t, ami megnehezíti a megfelel® m érték megtalálását. Ez amúgy is nehéz feladat, annak ellenére, hogy létezik m meghatározására polinomiális idej¶ algoritmus. Feltesszük, hogy a Randomgörbe(S) eljárás adott S algebrai struktúrához véletlenszer¶en szolgáltat egy E(S) elliptikus görbét. A Random-pont(En ) függvény egy véletlen P ∈ En pontot ad visszatérési értékként.
10.5. PRÍMTESZTELÉS ELLIPTIKUS GÖRBÉKKEL
121
GoldwasserKilian-prímteszt(n) 1 2 3
En ← Random-görbe(Z/nZ) m ← |En | if m = 2n1 nem áll el® úgy, hogy n1
then goto 1
4 5 6 7 8 9 10 11 12
valószín¶leg prím
P ← Random-pont(En ) 2P nem de niált
if if if if
13 14
then return összetett 2·P =O
then goto 5 mP 6= O
then return összetett n1
biztosan prím
then return prím else Goldwasser-Kilian-prímteszt(n1 )
Az
Atkin-teszt
kiváló példa egy olyan pontra, ahol a számelmélet három
területe, a prímtesztelés, az elliptikus görbék és a kvadratikus testek elmélete
összetalálkozik. Itt az alapgondolat az, hogy el®ször nem az p elliptikus görbét választjuk ki, hanem a rendjét. Ez úgy történik, hogy a
Q( (D))
képzetes
kvadratikus test algebrai egészei közt keresgélünk, és ha találunk olyan amelyre
|ν ± 1|
2
2
|ν| = n,
akkor
érdemes
olyan
m
számmal kísérletezni, amelyre
ν -t, m=
, azért, mert ha van ilyen és megfelel® módon faktorizálni is lehet, akkor a
megfelel®
E(Z/nZ) elliptikus görbe viszonylag könnyen megtalálható. Megfelel® m, azaz |E(Z/nZ)| = m.
alatt azt értjük, hogy a csoport rendje
A felhasznált kvadratikus testben nem mindegy, hogy hogyan választjuk meg
D alapdiszkriminánst. D negatív egésznek rendelkeznie kell D ≡ 0 (mod 4), vagy D ≡ 1 (mod 4), minden 2 D/k nem alapdiszkrimináns, D < −7. A NextD() eljárás egy
az úgynevezett
a következ® tulajdonságokkal:
k>1
egészre
megfelel®
D
értéket szolgáltat az alapdiszkriminánsok halmazából.
A gyakorlat azt mutatja, hogy a fenti feltételekkel rendelkez® alapdiszkriminánsok közül nem mindegyik
viselkedik egyformán, ezért nem véletlenszer¶en választunk. A választás stratégiáját most nem részletezzük, csak megemlítjük, hogy például a csupa kis faktorból álló alapdiszkriminánsok választása az átlagosnál nagyobb sikerrel kecsegtet, azaz kisebb eséllyel tér vissza az algoritmus
122
FEJEZET 10.
az els® lépéshez új
Adott zett
n
D
ELLIPTIKUS GÖRBÉK
értéket választani.
esetén és a hozzá megtalált
D
értékkel kiszámíthatjuk az úgyneve-
Hilbert-polinomot, amelynek tetsz®leges (mod n) vett gyökének segítsé-
gével megadhatunk két elliptikus görbét, amelyek rendje
2
m = |ν ± 1|
. Legyen
Hilbert(n, D) az a függvény, amely adott n-hez és D-hez szolgáltatja a Hilbert polinom egy gyökét. Felhasználjuk továbbá a GoldwasserKilian teszt ellen®rz® részét, de nem korlátozzuk
En , m , f
f
értékét. A
ahol természetesen
azaz felírható
m = f · n1
m
Bizonyíték függvény bemeneti értékei:
már keresztülment a megfelel® ellen®rzéseken,
alakban, ahol
f
faktorizációja ismert, és
n1
valószí-
összetett. Lehet
összetett, ha biztosan megkapjuk, hogy nem bizonyíték, ha a 7. lépésben tér vissza a program. Ez
n
vagy összetett, vagy a lehetséges kett®b®l a másik elliptikus
n¶leg prím. A kimeneti érték lehet
n
azt jelenti, hogy
görbét kellett volna választanunk. Végül lehet
bizonyíték
a kimenet, ekkor
következhet a rekurzió következ® lépése.
Bizonyíték(En , m, f ) 1 2 3 4 5 6 7 8
P ← Random(En ) f · P nem de niált
if
then return összetett
if
f ·P =O
if
mP 6= O
then goto 1
then return nem return igen
Most
már
nekifoghatunk
az
Atkin-teszt
ismertetésének.
10.5. PRÍMTESZTELÉS ELLIPTIKUS GÖRBÉKKEL
123
Atkin-prímteszt(n) 1 2 3 4
D ← NextD √ () ω ← (D + D)/2 if ∃ x, y ∈ Z : 4n = (2x + yD)2 − y2 D then ν ← x + yω
else goto 1
5 6 7
2
m ← |ν + 1| if m = f · n1 ,
then goto 12
8 9 10
13 14 15 16
23 24 25
√ 2 n1 > ( 4 n + 1)
nem áll el® úgy, hogy
n1
valószín¶leg prím) és
√ 2 n1 > ( 4 n + 1)
then return összetett else if Bizonyíték(En , m, f ) = igen then goto 23
19
21
valószín¶leg prím és
then goto 1
18
22
x0 ← Hilbert(n, D) c ← tetsz®leges egész, amire (c/n) = −1 k ← tetsz®leges egész, amire k ≡ x0 /(1728 − x0 ) (mod n) En ← {(x, y) | y 2 = x3 + 3kx + 2k} if Bizonyíték(En , m, f ) = összetett
17
20
n1
2
m ← |ν − 1| if m = f · n1
11 12
ahol
if if
En ← {(x, y) | y 2 = x3 + 3kc2 x + 2kc3 } Bizonyíték(En , m, f ) = összetett vagy Bizonyíték(En , m, f )
then return összetett n1
biztosan prím
then return prím else Atkin-prímteszt(n1 )
=
nem
124
FEJEZET 10.
ELLIPTIKUS GÖRBÉK
Irodalomjegyzék [1]
Saban Alaca, Kenneth S. Williams,
Introductory Algebraic Number
Theory, Cambridge University Press (2004) [2]
J. C. F. Gauss
[3]
J. L. Lagrange Recherches d'arithmétique, Nouv. Mém. Acad. Berlin III
Disquisitiones Arithmeticae (1801)
693-758, (1773) [4]
Hacéne Belbachir, Sadek Bouroubi, Abdelkader Khelladi, Connection Between Ordinary Multinomials, Fibonacci Numbers, Bell Polynomials and Discrete Uniform Distribution, Ann. Math. et Inf.
Vol 35 21-30,
(2008) [5]
Boris A. Bondarenko,
Generalized Pascal Triangles and Pyramids,
Their Fractals, Graphs and Applications, The Fibonacci Association, Santa Clara, (1993) [6]
R. Morton,
Pascal's Triangle and Powers of 11, Math. Teacher
Vol 57
392-394, (1964) [7]
S. Goldwasser, J. Kilian,
Almost all primes can be quickly certi ed,
Proceeding STOC '86 Proceedings of the eighteenth annual ACM symposium on Theory of computing, 316-329, (1986) [8]
A. O. L. Atkin, F. Morain, Mathematics of Computation
[9]
Elliptic Curves and Primality Proving,
Vol 61 (203) 29-68, (1993)
A. K. Lenstra, H. W. Lenstra Jr, Algorithms in number theory, Handbook of theoretical computer science 125
Vol A 673-715, (1990)
126
[10]
IRODALOMJEGYZÉK
Gábor Kallós, A Pascal háromszög általánosításai
(in Hungarian), Ma-
ster thesis, Eötvös Loránd University, Budapest, (1993) [11]
Gábor Kallós,
A Generalization of Pascal's Triangle Using Powers of
Base Numbers,Ann. Math. Blaise Pascal [12]
Vol 13 1-15, (2006)
Donald E. Knuth, The Art of Computer Programming, Addison-Wesley,
Vol 2 (1981)
[13] The On-line Encyclopedia of Integer Sequences, Publishedelectronically at
http://oeis.org [14]
(2010)
Wieb Bosma, Antal Járai, Gyöngyvér Kiss, for
elliptic
curve
primality
proofs,
Published
Better
http://www.math.ru.nl/∼bosma/pubs/reportfinal.pdf [15]
Edson Smith
at
(2009)
The Largest Known Primes, Published electronically at
http://primes.utm.edu/top20/page.php?id=3
[16]
paths
electronically
(2008)
Wieb Bosma, John Cannon, Catherine Playoust, gebra system. I. The user language, J. Symbolic Comput.,
The Magma al-
Vol 24 235-265,
(1997) [17]
K. H. Indlekofer - A. Járai,
Largest Known Twin Primes and Sophie
Germain Primes, Mathematics of Computation [18]
K. H. Indlekofer - A. Járai, tics of Computation.
[19]
Vol 68, 1317-1324 (1999).
Largest Known Twin Primes, Mathema-
Vol 65, 427-428 (1996).
T. Csajbók - G. Farkas - A. Járai - Z. Járai - J. Kasza, Report on the largest known twin primes, Annales Univ. Sci. Budapest, Sect. Comp.
Vol 25, 247-248 (2005). [20]
T. Csajbók - G. Farkas - A. Járai - Z. Járai - J. Kasza,
Report
on the largest known Sophie Germain and twin primes, Annales Univ. Sci. Budapest, Sect. Comp. [21]
H. Riesel, Comp.
Vol 26, 181-183 (2006).
Lucasian Criteria for the Primality of
Vol 23, 869-875 (1969).
N = h · 2n − 1,
Math.
IRODALOMJEGYZÉK
[22]
I. Kátai,
[23]
G. Steidl,
[24]
I. Kátai,
127
Generalized number systems and Fractal geometry, Pécs (1995) On symmetric representation of Gaussian integers, BIT,
29 563-571, (1989)
Number Systems in imaginary quadratic elds, Annales Univ.
Sci. Budapest., Sect. Comp. [25]
Vol 14 159-164, (1994)
I. Kátai, Construction of number systems in algebraic number elds, Annales Univ. Sci. Budapest., Sect. Comp.
[26]
I. Kátai, B. Kovács, W. J. Gilbert Appl.
[29]
Vol 42 99-107, (1980)
Canocical number systems in imaginary quadratic
elds, Acta Math. Hungar. [28]
Vol 18 103-107, (1999)
I. Kátai, B. Kovács, Kanonische Zahlensystemebei reelen quadratischen algebraischen Zahlen, Acta Sci. Math.
[27]
Vol
Vol 37 159-164, (1981)
, Radix representation of quadratic elds, J. Math. Anal.
Vol 83 264-274, (1991)
K. H. Indlekofer, A. Járai and I. Kátai,
On some properties of att-
ractors generated by iterated function systems, Acta. Sci. Math.
Vol 60
411-427, (1995) [30]
J.M. Thuswaldner, Fractals and number systems in real quadratic number elds, Acta Math. Hungar.
[31]
G. Farkas, Á. Fülöp
Vol 90(3) 253-269, (2001)
, The Sandbox Method in Quadratic Fields, An-
nales Univ. Sci. Budapest., Sect. Comp. [32]
T. Tél - T. Vicsek, J.Phys. A:Math. Gen.
[33]
Vol 28 235-248, (2008)
Geometrical multifractality of growing structures
Vol 20 L835, (1987)
F. Hausdorff, Dimension und ausseres Mass. Math. Ann. Vol 79 157-179 (1919)
[34]
B. Mandelbrot,
The Fractal Geometry of Nature Freeman, San Fran-
cisco, CA (1982) [35]
T. Tél - Á. Fülöp - T. Vicsek, Determination of fractal dimensions for geometrical multifractals, Physica A
Vol 159 155-166, (1989)
128
[36]
IRODALOMJEGYZÉK
H.G.E. Hentschel - I. Procaccia,
The in nite number of generalized
dimensions of fractals and strange attractors, Physica D
Vol 8
435-444,
(1983) [37]
K. Falconer,
Techniques in Fractal Geometry, (John Wiley & Sons),
England, (1997) [38]
R. H. Riedi,
An Improved Multifractal Formalism and Self-A ne Mea-
sures, Diss. ETH No. 10077 Doct of Math. (1993) [39]
P. Grassberger, I. Procaccia,
Estimation of the Kolmogorov entropy
from a chaotic signal, Phys. Rev. A ( [40]
Á. Fülöp, T.S. Biró,
Towards the Equation of State of Classical SU(2)
Lattice Gauge Theory, Phys. Rev. C [41]
Á. Fülöp,
Vol 28) 2591-2593, (1983) Vol 64 064902(5), (2001)
Determination of fractal dimensions and generalized entropies
for strange attractors, (Chaotic Dynamics: Theory and Practice) ed. by T. Bountis, (Plenum Press) New York, 49-52, (1992) [42]
Nour-Eddine Fahssi,
The Polynomial Triangles Revisited, J. Phys. A:
Math. Theor. (2012) [43]
L. Germán, A. Kovács, On number system constructions tica Hungarica
[44]
A. Kovács,
Vol 115 (1-2) 155-167, (2007)
On computation of attractors for invertible expanding linear
k
operators in Z
Proc. Numbers, Functions, Equations '98, Noszvaj, Hun-
gary, Lea ets in Mathematics [45]
Acta Matema-
Vol 56 (1-2) 97-120, (2000)
Farkas Gábor, Általánosított számrendszerek vizsgálata algebrai testb®vítésekben, PhD értekezés, ELTE IK Doktori Iskola (2001)
[46]
Gábor Farkas, Gábor Kallós, Triangles, Acta Tech. Jaur.
[47]
G. Farkas,
Number Systems in real quadratic elds, Annales Univ. Sci.
Budapest., Sect. Comp. [48]
Prime Numbers in Generalized Pascal
Vol 1 109-118 (2008)
Vol 18 47-59, (1999)
G. Farkas, Digital expansion in real algebraic quadratic elds, Mathematica Pannonica
Vol 10 (2) 235-248, (1999)
IRODALOMJEGYZÉK
[49]
129
G. Farkas, Location and number of periodic elements in Q Univ. Sci. Budapest., Sect. Comp.
[50]
G. Farkas,
Periodic elements and number systems in Q
tical and Computer Modelling [51]
G. Farkas, A. Kovács, Budapest., Sect. Comp.
[52]
Vol 20 133-146, (2001)
Vol 38 783-788, (2003)
Digital expansion in Q
Vol 22 83-94, (2003)
G. Nagy G. Nagy
Annales Univ. Sci.
Vol 23 123-135, (2004)
Vol 32 177-187, (2010)
On the simultaneous number systems of Gaussian integers, An-
nales Univ. Sci. Budapest., Sect. Comp. [55]
Mathema-
Remarks on the number systems of the Gaussian integers, An-
nales Univ. Sci. Budapest., Sect. Comp. [54]
√ 2 ,
G. Farkas, A. Kovács, Canonical expansions of integers in real quadratic elds, Annales Univ. Sci. Budapest., Sect. Comp.
[53]
√ 2 ,
√ 2 , Annales
Vol 35 223-238, (2011)
A. Schönhage, Fast reduction and composition of binary quadratic forms, In Proc. of ISSAC'91 128-133, (1991)
[56]
P. Bateman, R. Horn,
A heuristic asymptotic formula concerning the
distribution of prime numbers, Mathematics of Computation
Vol 16 363-
367, (1962) [57]
Járai, Antal
Számítógépes számelmélet, Published electronically at
http://compalg.inf.elte.hu/∼ ajarai/cnt.pdf [58]
(2009)
Farkas G., Fülöp Á., Gonda J., Járai A., Kovács A., Láng C., Székely J., Bevezetés a Matematikába Informatikai alkalmazásokkal, ELTE Eötvös Kiadó, ISBN 978 963 284 077 2, (2009)
[59]
I. R. Safarevics,
[60]
Freud Róbert, Gyarmati Edit,
Algebra, Typotex Kiadó, Budapest, (2000) Számelmélet, Nemzeti Tankönyvkiadó
Rt., Budapest, (2000) [61]
Washington,
Lawrence
HALL/CRC, (2003)
C.
Elliptic
Curves,
CHAPMAN
and
Tárgymutató Els®-Prímteszt, 69 Eratosztenész, 68 Jacobi, 33 Repeatedsquare, 22 SolovayStrassen-prímteszt,
Brun, Vigo, de, 56 Brun-konstans, 56
ciklikus csoport, 12 72
cinkos, 73 csoport törvény, 97
a n tér, 101 Agrawal, Manindra, 71
direkt szorzat, 13
AKS-algoritmus, 71
Dirichlet L-sor, 61
alapdiszkrimináns, 50, 121
Dirichlet, Johann Peter Gustav Lejeune (18051859), 19, 48
alapegység, 82 -1 normájú, 48
Dirichlet-tétel, 21
1 normájú, 48
diszkrét logaritmus probléma, 16
kvadratikus testben, 48
diszkrimináns, 49
algebrai
duplázás módszere, 110
egész, 37 elem, 37
ECPP, 8, 114
szám, 37
egész algebrai, 37
testb®vítés, 38 archiválandó forma, 76
elfajult kvadratikus test, 50
Atkin, A. O. L., 121 Atkin-prímteszt, 123
elliptikus görbe, 93 Elliptikus-Lenstra, 113
bázeli probléma, 62
Elliptikus-prímteszt, 120
Baker, Alan, 53
Eratosztenész, Syrenei (i.e. 276194), 67
Bateman-Horn-sejtés, 84 Bizonyíték, 122
eratosztenészi szita, 67 130
TÁRGYMUTATÓ
Euklidész, Alexandriai (i.e. 325265), 55
131
hangya, 80 Hasse tétel, 105
Euler, Leonhard (17071783), 15, 28
Hasse, Helmut (18981979), 105
Euler-féle azonosság, 61
Heilbronn, Hans Arnold (19081975), 52
Euler-kritérium, 28
Hilbert, David (18621943), 122 Fülöp, Ágnes, 127
Hilbert-polinom, 122
f®karakter, 17 faktorizáció, 56
ideálosztály csoport, 52
felbonthatatlan, 55
ideálosztályszám, 51, 52
Fermat, Pierre, de (16011655), 15
ikerprím, 55, 76
Fermat-szám, 116
ikerprím konstans, 86
fok
index, 16 algebrai elemé, 40
irreducibilis, 55
algebrai számé, 40
ismételt hatványozás, 21
Gauss, Johann Carl Friedrich (1777 1855), 31, 51, 58 Gauss-egészek, 44
Járai, Antal, 75 jó sorozat, 73 Jacobi,
Carl
Gustav
Jacob
1851), 30
Gauss-féle osztályszám probléma, 51 Gauss-féle számtest, 44
Jacobi-szimbólum, 30
Gauss-gy¶r¶, 55
John Pell, (1611-1685), 47
Gauss-sejtés, 52 generáló elem, 12
kandidátus, 77
generátor, 12
karakter
Germán, László, 128
Dirichlet, 19
Gilbert, W. J., 127
karakterisztika, testé, 35
Goldbach, Christian (16901764), 56
Kayal, Neeraj, 71
Goldwasser, Sha , 120
Kilian, Joe, 120
GoldwasserKilian-prímteszt, 121
konjugált
gyorshatványozás, 21
algebrai elemé, 41 Kovács, Attila, 128
hármas-szita, 78
Kovács, Béla, 127
hézag, 56
kriptográ a, 7
Hadamard, Jacques Salomon (1865
kritikus sáv
1963), 58
ζ
függvényé, 63
(1804
132
TÁRGYMUTATÓ
kvadratikus
Pell egyenlet, 47
forma, 50
Pockilngton-Lehmer prímteszt, 116
maradék, 27
Polard-féle
nemmaradék, 27
Polard-féle
reciprocitás törvénye, 31
Pollard, John Michael, 107
test, 43
Pollard-féle
kvadratikus test
λ módszer, 25 ρ módszer, 25 p−1
algoritmus, 107, 109
Pollard-pmínuszegy, 109
elfajult, 50
prím, 55 prím résztest, 36
Lagrange, Joseph Louis (17361813), 47
prímrekord, 56
Legendre, Adrien-Marie (17521833), 28
113
prímteszt, 7, 56 determinisztikus, 71
Lenstra, Hendrik Willem, 106
egzakt, 71
Linfoot, Edward Hubert (19051982), 53
projektív koordináták, 99
Lucas sorozat, 79 Edouard
nemdeterminisztikus, 71 primitív gyök, 16
Lucas kritérium, 81
Francois
prímszámtétel, 57 prímtest, 36
Lenstra elliptikus görbe algoritmusa,
Lucas,
prímfaktorizáció, 7
Anatole
(18421891), 114 Lucas-prímteszt, 116 Lucas-teszt, 114 Mersenne-prím, 7 Miller, George Abram (18631951), 72 MillerRabin-teszt, 72, 74 Miller-tétel, 74 minimálpolinom, 40
Proth, Francois (18521879), 79
résztest, 36 Rabin, Michael Oser, 72 redukált maradékosztályok multiplikatív csoportja, 14 Riemann -féle
ζ
függvény, 60
függvény, 59 Riemann sejtés, 64 általánosított, 65
norma kvadratikus testbeli elemé, 43
Riemann, Georg Friedrich Bernhard (18261866), 62 Riemann-sejtés
páratlan Goldbach-sejtés, 56 páros Goldbach-sejtés, 56
általánosított, 57 Riesel, Hans, Ivar, 79
TÁRGYMUTATÓ
Saxena, Nitin, 71 Smith, Edson, 7
133
Weierstrass egyenlet, 93 általánosított, 94
Solovay, Robert Martin, 72
Wilson, John (17411793), 69
Sophie Germain prím, 76
Wilson-féle kongruencia tétel, 69
Stark, Harold Mead, 53 Strassen, Volker, 72 számelmélet alaptétele, 55 törtideál, 51 tanú, 73 test 0-karakterisztikájú, 36 testb®vítés, 36, 38 algebrai, 38 egyszer¶, 38 foka, 39 véges, 38 végtelen, 38 valódi, 36 torziós pont, 103 transzcendens elem, 37 szám, 37 triviális gyök
ζ
függvényé, 63
véges kommutatív csoportok alaptétele, 15 véges logaritmus, 16 véges pont, 100 végtelen pont, 100 valódi, résztest, 36 Vallée Poussin, Charles Jean Gustave Nicolas, de la (18661962), 58 Vinogradov, Ivan Matvejevics (1891 1983), 56
