Prímtesztelés

Diplomamunka

Írta: Nagy Gábor

Alkalmazott matematikus szak

Témavezető:

Kátai Imre, egyetemi tanár Komputeralgebra Tanszék

Eötvös Loránd Tudományegyetem, Informatikai Kar

Eötvös Loránd Tudományegyetem Természettudományi Kar

Tartalomjegyzék

1. Bevezetés 1

1.1. Az RSA kriptorendszer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.1. Az RSA működése . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Prímteszt, prímtesztelés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3. Gyors hatványozás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2. Prímszámok 4 2.1. Alapok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2. Prímszámok karakterizációi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3. Speciális prímszámok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3. Valószínűségi prímtesztek 8 3.1. A Miller-Rabin teszt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2. A Solovay-Strassen teszt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.2.1. A Legendre- és Jacobi-szimbólumok . . . . . . . . . . . . . . . . . . . . . . 12 3.2.2. A Solovay-Strassen-teszt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

4. Prímtesztek speciális alakú prímek esetén 14 4.1. Mersenne-prímek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.2. Fermat-prímek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

5. Prímtesztelés elliptikus görbékkel 18 5.1. Elliptikus görbék . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.2. Prímtesztelés elliptikus görbékkel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

6. Az AKS-algoritmus 21

6.1. Az AKS-algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

6.1.1. Az algoritmus tökéletesítése . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 6.2. Az algoritmus megvalósíthatósága . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6.3. Lenstra és Pomerance változata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Irodalomjegyzék 30

1. fejezet

Bevezetés

„A prímeknek az összetett számoktól való megkülönböztetése és az összetettek felbontása prímek szorzatára az egész aritmetika egyik legfontosabb és leghasznosabb problémája. A tudomány méltósága megkövetelni látszik, hogy egy ilyen híres és elegáns probléma megoldásához

minden segédeszközt buzgón kifejlesszünk.”

Disquisitiones Arithmeticae(1801) Karl Friedrich Gauss

1.1. Az RSA kriptorendszer

Az RSA egy nyilvános kulcsú titkosítást megvalósító algoritmus. 1977-ben alkotta meg Ron Rivest, Adi Shamir, és Leonard Adleman.

1.1.1. Az RSA működése

Tegyük fel, hogy B szeretne titkosítva üzenni A-nak. A kulcsválasztás A választ két nagy véletlen prímszámot (egy véletlen szám utáni első prím). Legyenek ezek p és

q, a szorzatuk pedig n = p · q. Kiszámítjuk φ(n) értékét:

φ(n) = φ(p · q) = (p − 1)(q − 1) = p · q − p − q + 1 = n − p − q + 1

A választ még egy φ(n)-nél kisebb véletlen e számot, amire (e, φ(n)) = 1 (sok ilyen van). A kiszámolja e multiplikatív inverzét (mod φ(n)): d-t, amire e · d ≡ 1 (mod φ(n)). Az (n, e) számpár A nyilvános kulcsa, a (d, φ(n)) pedig a titkos kulcsa. Az algoritmus B címkézi az elküldendő üzenetet egy m 1 és n közötti számmal. B kiszámolja c = m^{e} (mod n)-et, ez lesz a titkosított üzenet. A beérkező üzenet elolvasása A által: m = c^{d} (mod n) meghatározása.

Valóban:

c^{d} ≡ (a^{e})^{d} = a^{e·d} = a^{k·φ(n)+1} = (a^{φ(n)})^{k} · a ≡ a (mod n),

mivel a^{φ(n)} ≡ 1 (mod n)(Euler-Fermat tétel).

Miért megfejthetetlen jelen ismereteink szerint?

Megfejteni csak d ismeretében lehet, ehhez viszont φ(n) kell. n ismeretében φ(n) kiszámítása viszont ekvivalens p, q kiszámításával, azaz n faktorizálásával. n olyan nagy, hogy jelen ismereteink szerint nem faktorizálható.

f(x) = x^{e} úgynevezett csapóajtófüggvény, azaz csak a d többletinformáció birtokában invertálható jelen ismereteink szerint.

Az RSA-hoz el kell dönteni egy véletlen szám utáni számokról, hogy azok prímek-e. Ez a következő kérdésre vezet: hogyan lehet eldönteni egy számról, hogy prím-e?

1.2. Prímteszt, prímtesztelés

1.2.1. Definíció. Prímteszt: egy kritérium arra, hogy egy n szám ne legyen prím. Ha n átmegy a teszten, lehet hogy prím, ha nem megy át (bukik), akkor biztos, hogy összetett.

Egy adott szám tesztelése prímségre több prímteszt egymás utáni alkalmazásából áll. Ez a prímtesztelés lehet:

a) valószínűségi – a tesztelést túlélő szám „nagy valószínűséggel” prím

b) determinisztikus – a tesztelést túlélő szám biztosan prím Példa:

a) Valamely n ∈ ℕ valamely a ∈ ℕ, a < n-nel való osztása ha a | n, akkor n nem prím. Ez egy prímteszt, melyet próbaosztástesztnek („trial division”) nevezünk

b) Ezt a próbaosztástesztet végrehajtva minden a ≤ \sqrt[3]{n}-re kapjuk, hogy n nem prím, ha a | n valamely ilyen a-ra. Csak kevés n szám éli túl: prímek, valamint az olyan összetett számok, amelyek két \sqrt[3]{n}-nél nagyobb prím szorzatai. A túlélők nagy valószínűséggel prímek, ezért ez egy elég jó valószínűségi prímtesztelést ad.

c) ∀a ≤ \sqrt{n}-nel osztva: ha bukik, akkor n biztosan összetett, ha nem, akkor biztosan prím. Ez determinisztikus tesztelés.

1.3. Gyors hatványozás

Az RSA-algoritmusban a titkosítás során meg kell határoznunk c = m^{e} (mod n)-et. Vajon ki tudjuk ezt gyorsan számolni? A válasz igen.

a, m ∈ ℤ számok esetén a^{m} meghatározásának műveletigénye ugyan O((log a)^{2} · m^{2}) vagyis O((log a)^{2} · e^{log m^{2}}), így lassú eljárás, viszont ha (mod n) tekintjük a hatványozást jobb helyzetben vagyunk:

1.3.1. Tétel. a^{m} (mod n) meghatározása O((log m) · (log n)^{2}) műveletet igényel.

Bizonyítás: Írjuk m-et diadikus alakban:

m = ε_{0} + ε_{1} · 2 + ε_{2} · 2^{2} + ⋯ + ε_{k} · 2^{k},

ahol ε_{i} ∈ {0, 1}, és k = O(log m). Legyen a_{i} az a^{2^{i}} szám maradéka (mod n) :

a_{i} ≡ a^{2^{i}} (mod n) 0 ≤ a_{i} < n i = 0, 1, …, k

Először határozzuk meg az a_{0}, a_{1}, …, a_{k}-t ebben a sorrendben:

a_{0} ≡ a^{2^{0}} = a (mod n)
a_{0} = a (feltéve: 0 ≤ a < n)

Ha a_{0}, …, a_{i} adottak, akkor a_{i+1} kiszámítása a következőképpen történik:

a_{i+1} ≡ a^{2^{i+1}} = a^{2^{i}·2} = (a^{2^{i}})^{2} = a_{i}^{2} (mod n)

Egy ilyen négyzetreemelés, majd az eredmény n-nel vett maradékának meghatározásának műveletigénye O((log n)^{2}).

a^{n} = a^{ε_{0}+ε_{1}·2+···+ε_{k}·2^{k}} = a^{ε_{0}} · a^{ε_{1}·2} ⋯ a^{ε_{k}·2^{k}} = ∏_{i=1}^{k} a^{ε_{i}·2^{i}} = ∏_{i=1}^{k} a_{i}^{ε_{i}}

vagyis azon a_{i}-k szorzata, melyekre ε_{i} = 1. Ezeket sorban szorozva egy-egy szorzás, majd (mod n) maradékvétel műveletigénye: O((log n)^{2}) Ezt k = O(log m)-szer végrehajtva a teljes műveletigény:

k · O(log n)^{2} = O((log m) · (log n)^{2}).

A gyors hatványozást a későbbiekben is fogjuk használni.

A továbbiakban adunk egy általános áttekintést a prímszámokról, majd bemutatunk néhány prímtesztelő eljárást, különös tekintettel az AKS-algoritmusra, amely az első polinomiális idejű determinisztikus prímteszt.

Prímszámok

2.1. Alapok

A prímszámokkal kapcsolatos kérdések több, mint kétezer éve foglalkoztatják az embereket. 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 definíciót.

2.1.1. Definíció. Legyen R gyűrű, és U(R) az egységek halmaza. Ekkor a p ∈ R^{∗} \ U(R) elem

1. felbonthatatlan(irreducibilis), ha minden a, b ∈ R esetén p = a · b-ből a ∈ U(R) vagy b ∈ U(R) következik

2. prím, ha minden a, b ∈ R esetén p = a · b-ből p | a vagy p | b következik.

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 felbonthatatlanok 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ában a felbonthatatlan elem definícióját használják prímekre.

Azt, hogy végtelen sok prímszám létezik, már Euklidész bizonyította, viszont a mai napig nem tudjuk, hogy az ikerprímek száma véges, vagy végtelen(p_{1}, p_{2} prímek ikerprímek, ha |p_{1} − p_{2}| = 2). Nagyon valószínű, hogy az x-nél kisebb ikerprímek száma aszimptotikusan cx/(ln^{2} x), alkalmas c konstanssal. 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 …,

az úgynevezett Brun-konstans. B értékének minél pontosabb meghatározása már a prímrekordok problémakörébe tartozik. Ezen a területen kerülnek terí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 páros Goldbachsejtés néven vált híressé. 1742-ben egy Eulernek írott levelében vetette 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 5-nél nagyobb páratlan szám előáll három prím összegeként, kapta a páratlan Goldbach-sejtés elnevezést. Megjegyezzük, hogy általában a páros eset vizsgá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 „nagy számokra”. Sajnos nagy számon, a későbbi tökéletesítések ellenére is 10 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 10^{17} nagyságrendig ellenőrzött, jól mutatja, hogy van még mit „lefaragni” az elméleti korlátból.

Talán a két legfontosabb prímszámokkal kapcsolatos fogalom a faktorizáció és a prímtesztelés. Előbbi azt jelenti, hogy adott számot megpróbálunk felbonthatatlanok 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 jegyű számokra is, addig a prímfaktorizációt legfeljebb 150-200 jegyű számokra hajthatjuk végre, legalábbis ez a helyzet 2005-ben. A legmodernebb titkosítási eljárások is azon alapulnak, hogy nagy számokat prímek szorzatára bontani „nehéz” feladat.

2.2. Prímszámok karakterizációi

2.2.1. Tétel. (kis Fermat-tétel)∀p ∈ P, (p, a) = 1 : a^{p−1} ≡ 1 (mod p)

A tétel speciális esete az Euler-Fermat tételnek:

2.2.2. Tétel. (Euler-Fermat) Ha (a, m) = 1, akkor a^{φ(m)} ≡ 1 (mod m).

Bizonyítás: Jelölje rendre r_{1}, r_{2}, …, r_{φ(m)} a redukált maradékosztályokat (mod m). Ha ezeket rendre beszorozzuk a-val, kapjuk: a · r_{1}, a · r_{2}, …, a · r_{φ(m)}. Azt állítjuk, hogy a kapott maradékosztályok páronként különbözőek: ha valamely i, j-re a · r_{i} ≡ a · r_{j} (mod m), akkor a · (r_{i} − r_{j}) ≡ 0 (mod m), s mivel a relatív prím mhez, ezért m | r_{i}−r_{j}, de ez ellentmond annak, hogy r_{i} és r_{j} különböző volt (mod m). Ezek szerint az a · r_{1}, a · r_{2}, …, a · r_{φ(m)} maradékosztályok sorrendtől eltekintve megegyeznek r_{1}, r_{2}, …, r_{φ(m)}-mel, és ezért a szorzataik megegyeznek:

r_{1} · r_{2} ⋯ r_{φ(m)} ≡ a · r_{1} · a · r_{2} ⋯ a · r_{φ(m)} (mod m)

Ezt rendezve:

r_{1} · r_{2} ⋯ r_{φ(m)} (a^{φ(m)} − 1) ≡ 0 (mod m)

s mivel r_{1} · r_{2} ⋯ r_{φ(m)} relatív prím m-hez, ezért m | a^{φ(m)} − 1, és pont ezt kellett bizonyítanunk. Ha m-et prímnek választjuk, akkor φ(m) = m − 1, és így azt kapjuk, hogy:

a^{m−1} ≡ 1 (mod m),

ami pont a kis Fermat-tétel állítása.

2.2.3. Tétel. Wilson-tétel: n ∈ P ⟺ (n − 1)! ≡ −1 (mod n)

Bizonyítás: Először tegyük fel, hogy n ∈ ℕ összetett szám. Ekkor van olyan d ∈ ℕ osztója, amelyre 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 (n − 1)! ≢ −1 (mod n).

Most legyen n prímszám! Ha n = 2, akkor (2 − 1)! = 1 ≡ −1 (mod 2) fennáll, tehát feltehetjük a továbbiakban, hogy n > 2. Tudjuk, hogy az ax ≡ 1 (mod n) kongruenciának pontosan egy megoldása van, ha (a, n) = 1. Ez n prím volta miatt teljesül minden 1 ≤ a ≤ n − 1 esetén. Vegyük észre, hogy a ≡ a^{−1} (mod n) csak az a ≡ 1 (mod n) és a ≡ n − 1 (mod n) esetben fordulhat elő. Mivel ∏_{a=1}^{n−1} a ≡ ∏_{a=1}^{n−1} a^{−1} (mod n) 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 Wilson-tétel jó összefüggést ad prímszámok felismerésére, hiszen egyetlen összetett számra sem teljesül, viszont prímtesztelésre sajnos nem használható, mert (n−1)! (mod n) nem számolható gyorsan.

2.2.4. Tétel. Legyen a, n ∈ ℤ, melyekre n ≥ 2 és (a, n) = 1 fennáll. Ekkor n akkor és csak akkor prím, ha

(x + a)^{n} ≡ x^{n} + a (mod n).  (2.1)

Bizonyítás: Tehát a feladatunk az f(x) = (x + a)^{n} − (x^{n} + a) polinom együtthatóinak vizsgálata (mod n). Rögtön adódik, hogy f(x) konstans tagja, illetve x^{n} együtthatója 0, továbbá 0 < i < n esetén minden x^{i} a binomiális tétel értelmében \binom{n}{i} · a^{n−i}-nel szorzódik. Az

\binom{n}{i} = \frac{n!}{i! · (n − i)!}

kifejezés mindig egész számot szolgáltat, tehát i! · (n − i)! osztója n!-nak.

Most tegyük fel, hogy n prímszám. Ekkor n nem osztója i! és (n − i)! egyetlen tényezőjének sem, tehát (n, i! · (n − i)!) = 1, ami azt jelenti, hogy i! · (n − i)! osztója (n − 1)!-nak. Kaptuk, hogy minden \binom{n}{i} kifejezés alkalmas b ∈ ℤ elemmel n · b alakban írható fel, ami kongruens 0-val (mod n).

Most azt az esetet vizsgáljuk, amikor n összetett. Bontsuk fel n-et prímhatványok szorzatára, és válasszunk a tényezők közül egy p^{k} számot, amire p^{k}||n. Ekkor p^{k} relatív prím a^{n−p}-hez és nem osztója \binom{n}{p}-nek. Ez azt jelenti, hogy f(x)-ben az x^{p}-es tag együtthatója nem osztható n minden faktorával, azaz n-nel sem, így:

\binom{n}{p} · a^{n−p} ≢ 0 (mod n).

Tehát, ha n nem prímszám, akkor f(x)-nek lesz 0-tól különböző együtthatója, így nem lehet nullpolinom ℤ_{n} felett.

Ez a tétel az utolsó fejezetben szereplő AKS-algoritmus alapja. Megjegyzés: A gyerekek a binomiális tételt gyakran rosszul jegyzik meg, és úgy gondolják, hogy (x + y)^{n} = x^{n} + y^{n}; ezt nevezték el a "gyerekek binomiális tételének". A tétel alapján teljesül az egyenlőség (mod n), ha n prímszám.

2.3. Speciális prímszámok

Mersenne-prímek

Vizsgáljuk meg, hogy egy 2^{n} − 1 alakú szám mikor lehet prímszám.

2.3.1. Állítás. Ha 2^{n} − 1 prímszám, akkor n prím.

Bizonyítás: Ha n = d·k, akkor 2^{n} −1 = (2^{d} −1)·(2^{d(k−1)} +2^{d(k−2)} +⋯+1). Tehát 2^{d} −1 | 2^{n} −1, ha d | n.

2.3.2. Definíció. A 2^{n} − 1 alakú számokat Mersenne-számoknak nevezzük, és M(n)-nel jelöljük

2.3.3. Definíció. A 2^{n} − 1 alakú prímeket Mersenne-prímeknek nevezzük.

A ma ismert legnagyobb prímek közül a legtöbb, köztük a legnagyobb is Mersenne-prím: 2^{25.964.951} − 1-nek 7.816.230 számjegye van, ez a 42. ismert Mersenne-prím, és 2005. február 18-án találta Dr. Martin Nowak.

Fermat-prímek

Nézzük meg, mi a helyzet a 2^{n} + 1 alakú számokkal:

2.3.4. Állítás. Ha 2^{n} + 1 prímszám, akkor n = 2^{m} alakú.

Bizonyítás: 2^{q·2^{m}} + 1 = (2^{2^{m}} + 1) · (2^{2^{m}·(q−1)} − 2^{2^{m}·(q−2)} + ⋯ + 2^{0})

2.3.5. Definíció. A 2^{2^{n}} + 1 alakú számokat Fermat-számoknak nevezzük, és F (n)-nel jelöljük.

2.3.6. Definíció. A 2^{2^{n}} + 1 alakú prímeket Fermat-prímeknek nevezzük.

F (0) = 3, F (1) = 5, F (2) = 17, F (3) = 257, és F (4) = 65537 prímek, ez alapján Fermat azt a sejtést állította fel, hogy az összes Fermat-szám prím. Ez nem igaz, hiszen F (5) = 4.294.967.297 = 641 · 6.700.417, sőt az előzőeken kívül nem ismerünk Fermat-prímet.

Pillai-prímek

A Wilson-tételből következik, hogy p | (p − 1)! + 1, ha p prím. Tehát p osztója f(p − 1) = (p − 1)! + 1-nek, és p ≡ 1 (mod p − 1). Felvetődhet a kérdés, hogy vajon f(n) = n! + 1 minden q prímosztójára teljesül-e a q ≡ 1 (mod n) összefüggés. A helyzet az, hogy 1 ≤ n ≤ 7-re igaz az állítás, de n = 8-ra már nem, ugyanis 8!+1-et osztja 61 és 661 is, viszont egyikük sem ≡ 1 (mod 8).

2.3.7. Definíció. A p prímet Pillai-prímnek nevezzük, ha található hozzá n ∈ ℕ úgy, hogy p | n!+1 és p ≢ 1(mod n).

Az első 15 Pillai-prím: 23,29,59,61,67,71,79,83,109,137,139,149,193,227,233. Egy egyszerű algoritmussal találhatunk Pillai-prímeket.

2.3.8. Tétel. Végtelen sok Pillai-prím van.

Valószínűségi prímtesztek

A kis Fermat-tételre alapozva születtek gyors futási idejű valószínűségi prímtesztek. Ezeknek az elve az, hogy n > 2 egész számra, ha

2^{n−1} ≢ 1 (mod n),

akkor n összetett. A

2^{n−1} ≡ 1 (mod n),

esetben nem mondhatjuk biztosan, hogy n nem prím. A gyakorlatban a valószínűségi tesztek jól használhatónak bizonyultak gyorsaságuk miatt, és amiatt, hogy kevés olyan összetett szám van, ami „átmegy” a teszten prím minősítéssel. Ezek a nem prímszámok, amelyek mégis prímként viselkednek bizonyos szituációkban, elrontva például prímtesztek determinisztikusságát, fontos szerepet játszanak a számelméleti kutatásokban, így nevesítjük is őket.

3.0.9. Definíció. Az n páratlan összetett számot a alapú pszeudoprímnek, vagy álprímnek nevezzük, ha

a^{n−1} ≡ 1 (mod n)

fennáll. Az n összetett számot Carmichael-számnak, vagy univerzális álprímnek nevezzük, ha minden (a, n) = 1 esetben fennáll az

a^{n−1} ≡ 1 (mod n)

kongruencia.

3.0.10. Tétel. Az n ∈ ℕ összetett páratlan szám akkor és csak akkor Carmichael-szám, ha az n = p_{1}^{α_{1}}p_{2}^{α_{2}} … p_{r}^{α_{r}} prímtényezős felbontásban α_{1} = α_{2} = ⋯ = α_{r} = 1 , r ≥ 3 és p_{i} − 1 | n − 1 (i = 1, 2, …, r) teljesül.

Carl Pomerance bizonyította az állítást, miszerint végtelen sok Carmichael-szám létezik.

Példa: az n = 91 = 7 · 13 szám 3 alapú pszeudoprím, de nem pszeudoprím a 2 alaphoz. Az n = 561 = 3 · 11 · 17 Carmichael-szám.

3.1. A Miller-Rabin teszt

Ebben a részben egy gyors(polinomiális idejű) prímtesztről, a Miller-Rabin tesztről lesz szó. Ez egy valószínűségi algoritmus, előfordulhat(csak kis valószínűséggel), hogy hibázik.

A fejezet további részére feltesszük, hogy az általunk tesztelni kívánt n egy 1-nél nagyobb páratlan egész.

Néhány valószínűségi prímteszt, beleértve a Miller-Rabin tesztet is, a következő általános struktúrával rendelkezik. Jelöljük ℤ_{n}^{+}-szal ℤ_{n} nemnulla elemeit; így: |ℤ_{n}^{+}| = n − 1, és ha n prím, akkor ℤ_{n}^{+} = ℤ_{n}^{∗}. Definiáljuk továbbá az L_{n} ⊂ ℤ_{n}^{+} halmazt a következőképpen:

• Létezik egy hatékony algoritmus annak eldöntésére, hogy adott n, és α ∈ ℤ_{n}^{+} esetén α ∈ L_{n} teljesül-e

• Ha n prím, akkor L_{n} = ℤ_{n}^{∗}

• Ha n összetett, akkor |L_{n}| ≤ c · (n − 1) valamilyen c < 1 konstansra

n prímségének teszteléséhez beállítunk egy t "hibaparamétert", és véletlenszerűen választunk α_{1}, …, α_{t} ∈ ℤ_{n}^{+}-t. Ha α_{i} ∈ L_{n} minden i = 1, …, t, akkor az output "igaz", különben pedig "hamis".

Könnyen látható, hogy ha n prím, akkor az algoritmus mindig "igaz" értékkel tér vissza, ha pedig összetett, akkor legfeljebb c^{t} valószínűséggel. Ha c = 1/2, és t-t elég nagynak választjuk, mondjuk t = 100, akkor a tévedés valószínűsége elhanyagolhatóan kicsi.

Teszünk egy kísérletet megfelelő L_{n} halmaz definiálására. Legyen:

L_{n} := {α ∈ ℤ_{n}^{+} : α^{n−1} = 1}.

Tudjuk, hogy L_{n} ⊂ ℤ_{n}^{∗}, mivel ha α^{n−1} = 1, akkor α-nak létezik multiplikatív inverze, mégpedig α^{n−2}. A gyors hatványozást használva annak eldöntése, hogy α ∈ L_{n} O((log n)^{3}) műveletet igényel.

3.1.1. Tétel. Ha n prím, akkor L_{n} = ℤ_{n}^{∗}. Ha n összetett, és L_{n} ⊊ ℤ_{n}^{∗}, akkor |L_{n}| ≤ (n − 1)/2.

Bizonyítás: Vegyük észre, hogy L_{n} a ℤ_{n}^{∗}-beli (n − 1)-edik hatványleképzés magja, és ezért ℤ_{n}^{∗} részcsoportja.

Ha n prímszám, akkor ℤ_{n}^{∗} rendje n − 1. Mivel a csoport rendje többszöröse az elemeinek rendjének, ezért α^{n−1} = 1 teljesül bármely α ∈ ℤ_{n}^{∗}, és így L_{n} = ℤ_{n}^{∗}.

Most tegyük fel, hogy n összetett, és L_{n} ⊊ ℤ_{n}^{∗}. Mivel részcsoport rendje osztója a csoport rendjének, ezért |ℤ_{n}^{∗}| = m · |L_{n}|, valamely m > 1 egészre. Ebből pedig következik, hogy:

|L_{n}| = \frac{1}{m}|ℤ_{n}^{∗}| ≤ \frac{1}{2}|ℤ_{n}^{∗}| ≤ \frac{n − 1}{2}.

Sajnos vannak olyan páratlan összetett számok, amelyekre L_{n} = ℤ_{n}^{∗}. Ezek a Carmichaelszámok.

Ahhoz, hogy egy jó prímtesztet kapjunk, egy új, Ln^{′} halmazt kell definiálnunk, amit a következőképpen teszünk meg. Legyen n − 1 = 2^{h} · m, ahol m páratlan és h ≥ 1, és legyen

Ln^{′} := {α ∈ ℤ_{n}^{+} : α^{m·2^{h}} = 1, és α^{m·2^{j+1}} = 1 ⇒ α^{m·2^{j}} = ±1, ha j ∈ {0, …, h − 1}}.

A Miller-Rabin teszt ezt az Ln^{′} halmazt használja L_{n} helyett. A definícióból adódik, hogy

L_{n} ⊆ Ln^{′}.

Annak eldöntése, hogy α ∈ ℤ_{n}^{+} Ln^{′}-höz tartozik-e a következő eljárással ellenőrizhető: β ← α^{m} if β = 1 then return true for j ← 0 to h − 1 do if β = −1 then return true if β = +1 then return false β ← β^{2} false

Világos, hogy ismételt négyzetreemelést használva az eljárás műveletigénye O((log n)^{3}).

3.1.2. Tétel. Ha n prím, akkor Ln^{′} = ℤ_{n}^{∗}. Ha n összetett, akkor |Ln^{′}| ≤ (n − 1)/4.

Bizonyítás: 1.eset: ha n prím. Legyen α ∈ ℤ_{n}^{∗}. Mivel ℤ_{n}^{∗} rendje n − 1, és elem rendje osztja a csoport rendjét, ezért α^{m·2^{h}} = α^{n−1} = 1. Most tekintsük valamely j ∈ {1, …, h − 1} indexet, amire α^{m·2^{j+1}} = 1, és legyen β := α^{m·2^{j}}. Mivel β^{2} = α^{m·2^{j+1}} = 1, ezért β lehetséges értékei: ±1. Ez azért van, mert ℤ_{n}^{∗} páros rendű ciklikus csoport, ezért pontosan két elem van, aminek a rendje osztja 2-t, ezek pedig +1 és

−1. Tehát Ln^{′} = ℤ_{n}^{∗}.

2.eset: n = p^{e}, ahol p prím és e > 1. Ln^{′}-t tartalmazza a ℤ_{n}^{∗}-beli n−1-edik hatványleképezés K magja. Tudjuk, hogy |K| = lnko(φ(n), n− 1). Mivel n = p^{e}, ezért φ(n) = p^{e−1} · (p − 1), és így

|Ln^{′}| ≤ |K| = lnko(p^{e−1} · (p − 1), p^{e} − 1) = p − 1 = \frac{p^{e} − 1}{p^{e−1} + ⋯ + 1} ≤ \frac{n − 1}{4}.

3.eset: n = p_{1}^{e_{1}} ⋯ p_{r}^{e_{r}} n prímfelbontása, r > 1. Jelölje R_{i}, i = 1, …, r a ℤ_{p_{i}^{e_{i}}} gyűrűt, és legyen

θ : R_{1} × ⋯ × R_{r} → ℤ_{n}

a kínai maradéktétel által adott gyűrűizomorfizmus. Legyen még φ(p_{i}^{e_{i}}) = m_{i}·2^{h_{i}}, ahol m_{i} páratlan, i = 1, …, r-re, és l := min{h, h_{1}, …, h_{r}}. Vegyük észre, hogy l ≥ 1, és minden egyes R_{i}^{∗} m_{i} · 2^{h_{i}} rendű ciklikus csoport.

Először belátjuk, hogy ha α ∈ Ln^{′}, akkor α^{m·2^{l}} = 1. Ennek a belátásához előszöris vegyük észre, hogy ha l = h, akkor definíció szerint α^{m·2^{l}} = 1, ezért tegyük fel, hogy l < h. Indirekt tegyük fel, α^{m·2^{l}} ≠ 1, és legyen j a legkisebb index az l, …, h − 1 tartományból, amire α^{m·2^{j+1}} = 1. Ln^{′} definíciója miatt α^{m·2^{j}} = −1. Mivel l < h, ezért l = h_{i} valamely i ∈ {1, …, r} indexre. α = θ(α_{1}, …, α_{r}) esetén α_{i}^{m·2^{j}} = −1. Ebből az követketik, hogy α_{i}^{m} multiplikatív rendje 2^{j+1}. Mivel j ≥ l = h_{i}, ezért ellentmondáshoz jutunk, mert egy csoport elemének (ebben az esetben α_{i}^{n}-nek) a rendje osztója a csoport (jelen esetben R_{i}^{∗}) rendjének.

Az előző bekezdés állításából, és Ln^{′} definíciójából következik, hogy α ∈ Ln^{′} implikálja α^{m·2^{l−1}} = ±1 összefüggést. Most tekintsünk egy kísérletet, melyben α-t véletlenül választjuk ℤ_{n}^{∗}-ból (egyenletes eloszlás szerint), és megmutatjuk, hogy ekkor P (α^{m·2^{l−1}} = ±1) ≤ 1/4, amiből következik a tétel.

Legyen α = θ(α_{1}, …, α_{r}). Mivel α egyenletes eloszlású ℤ_{n}^{∗}-on, ezért α_{i} egyenletes eloszlású R_{i}^{∗}-on, és az α_{i}-k függetlenek. Jelölje i = 1, …, r-re és j = 0, …, h-ra G_{i}(j) az m · 2^{j}-edik hatványleképezés képét R_{i}^{∗}-on. Tudjuk, hogy

|G_{i}(j)| = \frac{m_{i} · 2^{h_{i}}}{lnko(m_{i} · 2^{h_{i}}, m · 2^{j})}.

Mivel l ≤ h és l ≤ h_{i}, egyszerű számolással kapjuk, hogy:

|G_{i}(h)| | |G_{i}(l)| és 2|G_{i}(l)| = |G_{i}(l − 1)|.

Azaz G_{i}(l − 1) páros, és nem kisebb, mint 2|G_{i}(h)|. Abból, hogy G_{i}(l − 1) páros következik, hogy −1 ∈ G_{i}(l − 1). Az α^{m·2^{l−1}} = ±1 esemény pontosan akkor lép fel, ha (E_{1}) α^{m·2^{l−1}} = 1 i = 1, …, r vagy (E_{2}) α^{m·2^{l−1}} = −1 i = 1, …, r. Mivel az (E_{1}) és (E_{2}) események diszjunktak, és mivel az α^{m·2^{l−1}} értékek függetlenek, és α^{m·2^{l−1}} egyenletes eloszlású G_{i}(l − 1)-en, és G_{i}(l − 1) tartalmazza ±1-et, ezért azt kapjuk, hogy:

P (α^{m·2^{l−1}} = ±1) = P (E_{1}) + P (E_{2}) = 2 ∏_{i=1}^{r} \frac{1}{|G_{i}(l − 1)|},

és mivel |G_{i}(l − 1)| ≥ 2|G_{i}(h)|, ezért

P (α^{m·2^{l−1}} = ±1) ≤ 2^{−r+1} ∏_{i=1}^{r} \frac{1}{|G_{i}(h)|}.  (3.1)

Ha r ≥ 3, akkor 3.1 közvetlenül implikálja, hogy P (α^{m·2^{l−1}} = ±1) ≤ 1/4, és kész vagyunk. Tegyük fel, hogy r = 2. Ekkor n nem lehet Carmichael-szám, ezért valamely i ∈ {1, …, r}-re G_{i}(h) ≠ {1}, így |G_{i}(h)| ≥ 2, és ekkor 3.1-ből ismét következik P (α^{m·2^{l−1}} = ±1) ≤ 1/4, és ezzel befejeztük a bizonyítást.

3.2. A Solovay-Strassen teszt

3.2.1. A Legendre- és Jacobi-szimbólumok

3.2.1. Definíció. Legyen p > 2 prím és (a, p) = 1. Ekkor az a számot kvadratikus maradéknak nevezzük, ha megoldható az

x^{2} ≡ a (mod p)

kongruencia, és kvadratikus nemmaradéknak, ha nem oldható meg.

Megjegyezzük, hogy az a ≡ 0 (mod p) számokat egyik kategóriába sem soroljuk be.

3.2.2. Definíció. Legyen p páratlan prím. A Legendre-szimbólumot (\frac{a}{p})-vel jelöljük, és a következőképpen definiáljuk:

(\frac{a}{p}) = \{ \begin{matrix}0 & , ha p | a \\ 1 & , ha a kvadratikus maradék (mod p) \\ −1 & , ha a kvadratikus nemmaradék (mod p) \end{matrix}

Világos, hogy a_{1} ≡ a_{2} (mod p) esetén (\frac{a_{1}}{p} ) = (\frac{a_{2}}{p} ), továbbá

(\frac{a · b}{p}) = (\frac{a}{p}) · (\frac{b}{p})

A Legendre-szombólum azon tulajdonságát, amely több valószínűségi prímtesztelő algoritmus alapját képezi, Euler-kritériumnak nevezik.

3.2.3. Lemma. (Euler) Bármely p > 2 prímre és 0 < a < p-re

a^{\frac{p−1}{2}} ≡ (\frac{a}{p}) (mod p).

Nagy számok prímtesztelésénél gyakran használjuk a Legendre-szimbólum általánosítás tetszőleges egész számra:

3.2.4. Definíció. Legyen m = p_{1} · p_{2} ⋯ p_{n} páratlan egész, ahol p_{i}-k nem feltétlenül különböző prímek, és (a, m) = 1. Ekkor a következő szorzatot Jacobi-szimbólumnak nevezzük:

(\frac{a}{m}) = ∏_{i=1}^{n} (\frac{a}{p_{i}} ) .

Vegyük észre, hogy prímszámokra a Legendre- és Jacobi-szimbólum megegyezik. Könnyen belátható az alábbi hét állítás, melyek segítségével egyszerően kiszámolhatjuk a Jacobi-szimbólumot:

(1) a ≡ b (mod m) ⟹ (\frac{a}{m}) = (\frac{b}{m})

(2) (\frac{a·b}{m}) = (\frac{a}{m}) · (\frac{b}{m})

(3) (\frac{−1}{m}) = (−1)^{\frac{m−1}{2}}

(4) (\frac{2}{m}) = (−1)^{\frac{m^{2}−1}{8}}

(5) (\frac{a}{m}) · (\frac{a}{m′} ) = (\frac{a}{m·m′} )

(6) (\frac{a^{2}}{m} ) = (\frac{a}{m^{2}} )

(7) (\frac{a}{m}) = (−1)^{\frac{a−1}{2} · \frac{m−1}{2}} · (\frac{m}{a})

3.2.2. A Solovay-Strassen-teszt

Az Euler-kritérium vizsgálatán alapszik a Solovay-Strassen-teszt néven ismert eljárás, amelynek ismertetésénél felhasználjuk a Jacobi(a,n) eljárást, ami kiszámolja az (\frac{a}{m}) Jacobi-szimbólumot, illetve a Random(x,y) függvényt, ami egy véletlen számot ad az [x, y] intervallumból.

Solovay-Strassen-prímteszt(n)

1. d ← Random(1,n)

2. if a^{(n−1)/2} ≢ Jacobi(a,n) (mod n)

3. then return Összetett

4. else return Valószínűleg prím

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 „téved”, azaz n bemeneti érték esetén legfeljebb (n − 1)/2 összetett szám elégíti ki a vizsgált 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ő.

Prímtesztek speciális alakú prímek

esetén

4.1. Mersenne-prímek

4.1.1. Tétel. Legyen p prím, s_{1} = 4, s_{k} = s_{k−1}^{2} − 2, k = 1, 2, . . .. Az M(p) szám akkor és csak akkor prím, ha M(p) az s_{p−1} osztója.

Bizonyítás: Először néhány segédtételt és észrevételt közlünk. Legyen α = 1 + \sqrt{3}, \overline{α} = 1 − \sqrt{3}, továbbá E_{n} := \frac{α^{n}−\overline{α}^{n}}{α−\overline{α}} , F_{n} := α^{n} + \overline{α}^{n}. Nyilvánvaló, hogy α + \overline{α} = 2 és α\overline{α} = −2. A binomiális tételből következik, a (0) észrevétel.

(0) E_{n} = \binom{n}{1} + \binom{n}{3} · 3 + \binom{n}{5} · 3^{2} + …, F_{n} = 2 · \{1 + \binom{n}{2} · 3 + \binom{n}{4} · 3^{2} + … \}

(1) 2E_{k+l} = E_{k} · F_{l} + F_{k} · E_{l}

(2) (−2)^{l+1} · E_{k−l} = E_{l} · F_{k} − E_{k} · F_{l} k > l

(3) E_{2k} = E_{k} · F_{k}

(4) F_{2k} = F_{k}^{2} + (−2)^{k+1}

(5) F_{k}^{2} − 12E_{k}^{2} = (−2)^{k+2}

(6) 2F_{k+l} = F_{k} · F_{l} + 12E_{k} · E_{l}

Adott páratlan q prímre jelölje ω(q) azt az n legkisebb pozitív egész számot, amelyre q|E_{n}. Ha nincs ilyen n, akkor ω(q) = ∞.

4.1.2. Lemma. Legyen S = {ν ∈ ℕ, q | E_{ν}}. Ekkor

S = {k · ω(q) |k ∈ ℕ}.

Bizonyítás: Ha k, l ∈ S, akkor (1) és (2) miatt k + l, és k > l esetén k − l ∈ S. Ezért ω(q) többszörösei S-hez tartoznak. Tegyük fel indirekt módon, hogy létezik m ∈ S, amelyre ω(q) ∤ m. Ekkor m = l · ω(q) + r, 0 < r < ω(q), és m ∈ S, l · ω(q) ∈ S miatt

m − l · ω(q) = r ∈ S.

Ez ellentmond ω(q) definíciójának.

4.1.3. Lemma. Ha q > 3 prím, akkor

(7) q|E_{q} − 3^{\frac{q−1}{2}} , és

(8) q|F_{q} − 2

Bizonyítás: (0) és q | \binom{q}{j} 1 ≤ j ≤ q − 1 miatt

E_{q} ≡ \binom{q}{q} · 3^{\frac{q−1}{2}} ≡ 3^{\frac{q−1}{2}} (mod q)

valamint

F_{q} ≡ 2 (mod q).

4.1.4. Lemma. Ha q > 3 prím, és ω(q) létezik, akkor

ω(q) ≤ q + 1.

Bizonyítás: E_{1} = 1, F_{1} = 2. Alkalmazzuk a az (1) és (2) egyenlőségeket k = q és l = 1 választással. Ekkor 2E_{q+1} = 2E_{q} + F_{q}, −4E_{q−1} = 2E_{q} − F_{q}, azaz

−8E_{q−1} · E_{q+1} = 4E_{q}^{2} − F_{q}^{2} ≡ 4 · 3^{q−1} − 4 ≡ 0 (mod q)

s ezért

q | E_{q−1} · E_{q+1},

amivel a lemma bizonyítását befejeztük.

4.1.5. Lemma. Ha p ≡ 7 (mod 12), akkor (\frac{3}{p}) = −1, és így

p | 3^{\frac{p−1}{2}} + 1.

Bizonyítás: Legyen p ≡ 7 (mod 12). Ekkor

(\frac{3}{p}) = (−1)^{\frac{p−1}{2} · \frac{3−1}{2}} · (\frac{p}{3}) = −1 · (\frac{p}{3}) = −1.

Most rátérünk a tétel elegendőségének bizonyítására. Legyen p páratlan prím, és M(p) | s_{p−1}. Ekkor

(9) M(p) | 2^{2^{p−2}} · s_{p−1}. Belátjuk, hogy F_{2^{n}} = 2^{2^{n−1}} · s_{n} (n = 1, 2, …). Mivel 2s_{1} = F_{2}, ez igaz, ha n = 1. Tegyük fel, hogy beláttuk az állítást n-ig. Mivel s_{n+1} = s_{n}^{2} − 2, ezért

2^{2^{n}} · s_{n+1} = (2^{2^{n−1}} · s_{n})^{2} − 2^{2^{n}+1}.

(4) miatt k = 2^{n}-re:

F_{2^{n+1}} = F_{2^{n}}^{2} − 2^{2^{n}+1},

ezért

F_{2^{n+1}} = 2^{2^{n}} · s_{n+1},

így n = p − 1-re

(10) 2^{2^{p−2}} · s_{p−1} = F_{2^{p−1}}. Ekkor (9) és (10) miatt

(11) M(p) | F_{2^{p−1}}, ahonnan (3)-at k = 2^{p−1}-re alkalmazva kapjuk, hogy

(12) M(p)|E_{2^{p}}. Legyen most q prím, q | M(p). Ekkor q ≠ 2, 3, tehát q > 3. (12) miatt q | E_{2^{p}}. Ekkor 4.1.2 miatt ω(q) | 2^{p}. Ha ω(q) ≠ 2^{p} teljesülne, akkor ω(q) | 2^{p−1} lenne, és így q | E_{2^{p−1}} fennállna. Ekkor (11) és (5) miatt q valamely 2-hatvány osztója lenne, ami nem lehet. Tehát ω(q) = 2^{p}. 4.1.4 miatt 2^{p} ≤ q + 1, azaz q ≥ 2^{p} − 1 = M(p), q|2^{p} − 1, és így q = M(p), amivel az elégségességet beláttuk.

A tétel szükségességének bizonyításához legyen p > 2, M(p) = q prím. Ekkor 8 | 2^{p} = q + 1, q ≡ 7 (mod 8). Mivel p páratlan, ezért

q = 2^{p} − 1 ≡ 2 − 1 ≡ 1 (mod 3),

és így q ≡ 7 (mod 24), azaz q = 24r + 7 alakban írható alkalmas r ∈ ℕ_{0}-ra. Alkalmazzuk (4)-et k = 2^{p−1} választással. Ekkor:

(13) F_{2^{p}} = F_{2^{p−1}}^{2} − 4 · 2^{2^{p−1}−1}. Mivel q = 24r + 7 = 8 · 3r + 7, ezért

q | M (\frac{q − 1}{2}) = 2^{\frac{q−1}{2}} − 1.

Ez a

(\frac{2}{q}) = (−1)^{\frac{q^{2}−1}{8}} = 1

és a

2^{\frac{q−1}{2}} ≡ (\frac{2}{q}) (mod q)

formulából azonnal következik. Mivel M (\frac{q−1}{2}) = M(2^{p−1} − 1), ezért q | 2^{2^{p−1}−1} − 1, ahonnan (14) q | F_{2^{p}} − F_{2^{p−1}}^{2} + 4. (6)-ot k = q és l = 1 választással alkalmazva, q + 1 = 2^{p} miatt:

2F_{2^{p}} = F_{q}F_{1} + 12E_{q}E_{1} = 2F_{q} + 12E_{q}.

Tehát

(15) F_{2^{p}} = F_{q} + 6E_{q} = (F_{q} − 2) + 6(E_{q} + 1) − 4. A 4.1.5 miatt q | 3^{\frac{q−1}{2}} + 1, továbbá (7) miatt q | E_{q} + 1, (8) miatt q|F_{q} − 2. Ezért (15) miatt q | F_{2^{p}} + 4, és így (14) miatt q | F_{2^{p−1}}^{2}. (10) miatt, q = M(p) páratlan volta miatt M(p) | s_{p−1}. A szükségességet beláttuk, ezáltal a tételt is.

Tekintsük most az algoritmust, aminek a bemenete egy m > 2 páratlan egész szám. Lucas-Lehmer-prímteszt(m)

1. M ← 2^{m} − 1

2. v ← 4

3. for i ← 1 to m − 2

4. do v ← v^{2} − 2

5. if v ≡ 0 (mod M)

6. then return prím

7. else return összetett

4.2. Fermat-prímek

4.2.1. Tétel. Ha F_{m} jelöli a 2^{2^{m}} + 1 alakú Fermat-számot, akkor m > 1 esetén F_{m} akkor és csak akkor prím, ha 5^{(F_{m}−1)/2} ≡ −1 (mod F_{m}) Bizonyítás: Mivel F_{m} −1 egyetlen prímosztója 2, a kongruencia teljesülése esetén F_{m} prím, hiszen ekkor 5 rendje F_{m} − 1 (mod F_{m}). A másik irány bizonyításához azt kell megmutatnunk, hogy 5 kvadratikus nemmaradék mod F_{m}. Tudjuk, hogy 2^{4} ≡ 1 (mod 5) Mivel 2^{m} 4 többszöröse, ezért: F_{m} = 2^{2^{m}} + 1 ≡ 2 (mod 5). Az (\frac{5}{F_{m}} ) Legendre-szimbólum a kvadratikus reciprocitási tétellel számolva: (\frac{5}{F_{m}} ) = (\frac{F_{m}}{5} ) = (\frac{2}{5}) = −1

Prímtesztelés elliptikus görbékkel

5.1. Elliptikus görbék

Egy elliptikus görbe ℝ felett azon síkbeli (x, y) párok halmaza, amelyek kielégítik az

y^{2} = x^{3} + a · x + b

egyenletet, ahol a, b valós konstansok, amelyekre 4a^{3} + 27b^{2} ≠ 0. Világos, hogy ha az (x, y) pont a görbén van, akkor az (x, −y) pont is. (A 4a^{3} + 27b^{2} ≠ 0 feltétel azt biztosítja, hogy az f(x, y) = 0, f(x, y) = y^{2} − x^{3} − a · x − b görbe minden (x_{0}, y_{0}) pontjában létezzen egyértelmű érintő.) Ha egy (nem függőleges) egyenes metszi ezt a görbét két pontban, akkor egy harmadikban is. A görbe egy érintőjét úgy tekintjük, mint amelynél a két metszéspont egybeesik.

Ha (x_{1}, y_{1}) és (x_{2}, y_{2}) a két metszéspont, akkor a harmadik koordinátái:

x_{3} = λ^{2} − x_{1} − x_{2}, y_{3} = λ · (x_{3} − x_{1}) + y_{1}

ahol

λ = \frac{y_{2} − y_{1}}{x_{2} − x_{1}} , ha x_{1} ≠ x_{2} és egyébként λ = \frac{3x_{1}^{2} + a}{2y_{1}}.

Világos, hogy λ az egyenes meredeksége. Érintő esetén ezt az implicit függvény differenciálásával kapjuk.

Az (x_{1}, y_{1}) + (x_{2}, y_{2}) = (x_{3}, −y_{3}) összefüggéssel egy összeadást definiálhatunk. Ha a függőleges egyeneseknek megfelelő ∞ szimbólumot, mint nullelemet definiáljuk, azaz

(x, y) + (x, −y) = (x, −y) + (x, y) = ∞,

akkor megmutatható, hogy egy Abel-csoportot kapunk.

Ha a, b racionálisak, tekinthetünk csak racionális koordinátájú pontokat, és egy másik csoportot kapunk. Általánosabban, tekinthetünk elliptikus görbéket egy tetszőleges 𝔽 felett, amelynek karakterisztikája különbözik 2-től és 3-tól. Meg lehet mutatni, hogy mindig Abel-csoportot kapunk. Még ha csak egy egységelemes kommutatív gyűrű adott, például ℤ/nℤ, lnko(n, 6) = 1, akkor is definiálhatjuk a fenti műveleteket parciálisan, azaz ha az osztás elvégezhető; természetesen ekkor nem kapunk csoportot. Fontos azonban észrevennünk, hogy ha lnko(n, 4a^{3} +27b^{2}) = 1, akkor bármely p prímosztójára n-nek modulo p is egy elliptikus görbét kapunk, és ha ℤ/nℤ felett el tudunk végezni egy összeadást, akkor bármely p prímosztójára n-nek, az eredmény (mod p) redukálva ugyanaz, mintha előbb elvégezzük a (mod p) redukálást, és aztán végezzük el a műveletet (mod p). (A ∞ szimbólum redukálva saját maga.)

Prímteszteléshez csak ilyen, modulo n vett elliptikus görbékre lesz szükségünk.

5.1.1. Tétel. (Hasse tétele) Ha p > 3 prím, akkor egy ℤ/pℤ felett vett elliptikus görbe rendje p + 1 − 2\sqrt{p} és p + 1 + 2\sqrt{p} között van.

Meg lehet mutatni azt is, hogy az elliptikus görbék rendje meglehetősen egyenletesen oszlik el ebben az intervallumban, legalábbis az intervallum közepén.

5.2. Prímtesztelés elliptikus görbékkel

Az elliptikus görbékkel történő prímtesztelés az alábbi tételen alapszik:

5.2.1. Tétel. Legyen n ∈ ℕ, lnko(6, n) = 1 és legyen E_{n} egy ℤ/nℤ feletti elliptikus görbe pontjainak a halmaza. Legyenek m és s egészek úgy, hogy s | m. Tegyük fel, hogy találtunk olyan P pontot E_{n}-ben, amelyre

m · P = 0 és \frac{m}{q} · P ≠ 0

q minden prímfaktorára s-nek. Ekkor minden p prímosztójára n-nek |E_{p}| ≡ 0 (mod s). Továbbá, ha s > (\sqrt[4]{n} + 1)^{2}, akkor n prím.

Bizonyítás: Legyen p egy prímosztója n-nek, és legyen

Q = \frac{m}{s} · P_{p} ∈ E_{p}.

Ekkor s · Q = m · P_{p} = (m · P)_{p} = 0, így Q rendje osztja s-et. Ha q egy prímosztója s-nek, akkor

\frac{s}{q} · Q = \frac{m}{q} · P_{p} = (\frac{m}{q} · P)_{p} ≠ 0, mivel \frac{m}{q} · P ≠ 0

Így Q rendje nem osztója s/q-nak. Mivel q tetszőleges volt, Q rendje s, így |E_{p}| = 0 (mod s).

Hasse tétele szerint |E_{p}| = p + 1 − t valamely |t| ≤ 2\sqrt{p} egészre. Ebből (p^{1/2} + 1)^{2} ≥ |E_{p}|. Ha s > (n^{1/4} + 1)^{2}, akkor azt kapjuk, hogy (\sqrt{p} + 1)^{2} > (n^{1/4} + 1)^{2}, amiből p > \sqrt{n}.

A prímtesztek vázlata:

Az n valószínű prím prím voltának bizonyításához válasszunk egy elliptikus görbét ℤ/nℤ felett, és egy m számot, amelyre a görbe rendje m – legalábbis ha n prím. Ha m felírható f · n_{1} alakban, ahol f faktorait ismerjük, n_{1} pedig valószínű prím, és n_{1} > (n^{1/4} + 1)^{2}, akkor n prím voltát ezen pont első tétele segítségével be tudjuk bizonyítani. Válasszunk ugyanis egy olyan P pontot, amely eleget tesz a tétel feltételeinek s = n_{1} választással. Ehhez válasszunk egy véletlen P pontot a görbén(x véletlen, y-t kiszámítjuk). Számítsuk ki (m/n_{1}) · P = f · P -t; ha nincs definiálva, akkor megtaláltuk n_{1} egy valódi osztóját, ami nagyon valószínűtlen. Annak valószínűsége, hogy k · P = 0 legyen, az előző tétel szerint kisebb, mint 1/2, ha n prím, ebben az esetben válasszunk új pontot.

Egyébként ellenőrizzük, hogy n_{1} · (f · P) = m · P = 0, aminek teljesülnie kell, ha n prím. Így P létezése bizonyítja, hogy n prím, ha n_{1} prím. Most alkalmazzuk az eljárást n_{1}-re, stb.

A Goldwasser-Kilian teszt. A fenti gondolat Goldwassertől és Kiliantól származik. Javaslatuk szerint véletlenszerűen választunk egy elliptikus görbét ℤ/nℤ felett, meghatározzuk m-et, és ha f = 2 választással teljesülnek a fenti feltételek, akkor megyünk tovább. Természetesen a gyakorlatban nem érdemes f-et korlátozni, hanem m kis faktorait próbaosztással keressük meg. A módszerrel az a probléma, hogy egy véletlen elliptikus görbére m-et meghatározni nagyon nehéz, bár van rá polinomiális futásidejű (O(n^{8})) algoritmus.

Atkin tesztje. A teszt alapgondolata az, hogy megfordítjuk m és a görbe megválasztásának sorrendjét. Ezt úgy érjük el, hogy egy alkalmas D negatív egészre a ℚ(\sqrt{D}) test ν egészei között keresünk egy olyat, amelyre |ν|^{2} = n (ha van ilyen). Ha ez megvan, akkor m = |ν ± 1|^{2} rendű elliptikus görbéket „könnyen” találhatunk. Így m-et már akkor tudjuk, amikor a görbét még nem: azt ráérünk később is meghatározni.

Az AKS-algoritmus

6.1. Az AKS-algoritmus

Az esetleges félreértések elkerülése végett teszünk néhány megjegyzést a fejezetben használt jelölésekkel kapcsolatban. log minden esetben kettes alapú logaritmust jelöl. A bonyolultságelméletből ismert fogalmakat a szokásos módon értelmezzük. A szakirodalomban algoritmusok vizsgálatánál általában n bites bemenetet tételeznek fel, és n függvényében vizsgálják a futási időt. Prímtesztek esetéban viszont, ha n pozitív egész a vizsgálandó szám, akkor ábrázolásához ⌈log(n)⌉ bitre van szükség, tehát a bonyolultsági korlátok ⌈log(n)⌉ függvényeiben értendőek. Használni fogjuk továbbá a Õ(t(n)) kifejezést O(t(n) · poly(log t(n))) jelölésére, ahol t(n) tetszőleges függvénye n-nek, és poly(log t(n)) polinomiális függvénye log t(n)-nek, azaz

poly(log t(n)) = a_{0} + a_{1} log t(n) + ⋯ + a_{r} log^{r} t(n),

valamely r pozitív egészre, és a_{0}, a_{1}, …, a_{r} valós együtthatókra. Például, ha t éppen a log függvénnyel egyenlő, akkor

Õ(log^{k}(n)) = O(log^{k}(n) · poly(log log n)) = O(log^{k+ε} n)

tetszőleges pozitív ε-ra.

Agrawal, Kayal és Saxena 2002-ben közöltek egy algoritmust, 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 ⌈log n⌉-nek polinomiális függvénye. Ráadásul ez az algoritmus determinisztikus, vagyis a valószínűségi tesztekkel ellentétban itt a legkisebb esélye sincs annak, hogy valamely álprímet véletlenül prímnek nyilvánítsunk.

Az algoritmus a 2.2.4 tételen alapszik. Az alapgondolat: bemenetként adott n természetes számhoz keressünk megfelelő a egészet és ellenőrizzük, hogy teljesül-e a 2.1 kongruencia. Ez így természetesen nagyon egyszerű, de mivel mintegy n tagról kell eldönteni, hogy kongruens-e 0-val (mod n), nem hatékony eljárás. A továbbiakban szeretnénk a számolásokat egy megfelelően választott relatíve kevés elemből álló véges struktúra felett végezni, azt remélve, hogy így le tudjuk csökkenteni f(x) vizsgálandó együtthatóinak számát.

Az algebrában jól ismert tény, hogy tetszőleges R főideálgyűrűben R/⟨a⟩ akkor és csak akkor lesz test. ha a felbonthatatlan elem R-ben. ⟨a⟩ itt az a elem által generált főideált jelenti. Tehát tekintsük az F_{p} véges test feletti h(x) d-edfokú irreducibilis, azaz felbonthatatlan polinomot. Ekkor F_{p}[x]/⟨h(x)⟩ egy p^{d} elemszámú testet alkot, amelynek elemei az F_{p} feletti legfeljebb (d − 1)-edfokú polinomok. A továbbiakban alkalmazzuk a következő jelölést: ha f(x) ≡ g(x) teljesül ℤ_{n}/⟨h(x)⟩- ben, akkor azt írjuk, hogy

f(x) ≡ g(x) (mod n, h(x).

Megjegyezzük, hogy ℤ_{n} akkor és csak akkor alkot testet, ha n prímszám, tehát a ℤ_{n}[x]/⟨h(x)⟩ gyűrű nem feltétlenül test, és legfeljebb (deg(h(x)) − 1)-edfokú polinomkifejezésekből áll, amelyek együtthatói ℤ_{n}-beliek. Az AKS-algoritmusban h(x) = x^{r} −1, ahol r egy „megfelelően kicsi” pozitív egész. A továbbiakban természetesen a „megfelelően kicsi” kifejezés értelmét pontosítjuk. Tehát a prímek azonosítására használjuk 2.1 helyett a

(x + a)^{n} ≡ x^{n} + a (mod n, x^{r} − 1)  (6.1)

kongruenciát. A 2.2.4 tételből közvetlenül következik, hogy ha n prímszám, akkor kielégíti a 6.1 összefüggést, minden a és r esetén. Látható továbbá, hogy ha r elég kicsi n-hez képest, akkor kevesebb együtthatót kell megvizsgálnunk. Sajnos cserébe azt az árat kell fizetnünk, hogy bizonyos a és r értékek esetén előfordulhat, hogy valamely n összetett szám is kielégíti a kongruenciát. Viszont bizonyítható, hogy megfelelően választott r esetén nem túl sok a értékre elvégezve a vizsgálatot, csak olyan összetett számok mehetnek át a teszten, amelyek prímhatványok. Az AKS-algoritmus annak köszönheti a gyorsaságát, hogy mind r értékére, mind a különböző a-k számára olyan felső korlát adható, amely ⌈log n⌉-nek polinomiális függvénye. Ezen tények, és az, hogy n-ről eldönteni prímhatvány mivoltát nem tart sokáig, eredményezi a ⌈log n⌉-ben polinomiális futási időt. Ráadásul, ahogy azt a későbbiekben látni fogjuk, ennyi vizsgálat is elég ahhoz, hogy n prím voltát száz százalékos biztonsággal eldöntsük, azaz az algoritmus determinisztikus is, ami miatt kiemelkedik az eddig ismert prímtesztek közül.

Az algoritmus lépései

• Megvizsgáljuk, hogy n teljes hatvány-e. Ennek a lépésnek a műveletigénye Õ((log n)^{3})

• Keresünk egy r egészet, amire n rendje mod r > (log n)^{2}. Ennek a kézenfekvő módja, hogy kiszámítjuk n^{j} (mod r)-et j = 1, …, [(log n)^{2}]-re és minden q > [(log n)^{2}] egészre, az első q-ig, amire a maradékok egyike sem 1. Az így megtalált q jó lesz r-nek. r megtalálása Õ(r·(log n)^{2}) lépés.

• Meghatározzuk, hogy (a, n) > 1 teljesül-e valamely a ≤ r-re, amihez Õ(r · (log n)^{2}) művelet kell.

• Ellenőrizzük, hogy fennáll-e az (x+a)^{n} ≡ x^{n}+a (mod n, x^{r} −1) összefüggés a = 1, 2, …, [\sqrt{r}· log n]-re. Egy ilyen kongruencia ellenőrzésének műveletigénye Õ(r · (log n)^{2}), így a teljes műveletigény Õ(r^{\frac{3}{2}} · (log n)^{3}).

Be fogjuk látni, hogy létezik megfelelő r ≤ 2(log n)^{5}, és így az algoritmus műveletigénye: Õ((log n)^{10,5}).

Agrawal, Kayal és Saxena tételének bizonyítása:

Feltesszük, hogy adott egy n > 1 egész, ami nem teljes hatvány, nincs r-nél kisebb prímosztója, a rendje d > (log n)^{2} (mod r), és

(x + a)^{n} ≡ x^{n} + a (mod n, x^{r} − 1)  (6.2)

minden a-ra: 1 ≤ a ≤ A, ahol A = \sqrt{r} · log n A 2.2.4 tétel miatt tudjuk, hogy ezek a feltételek teljesülnek, ha n prím, tehát azt kell bizonyítanunk, hogy nem állhatnak fönt, ha n összetett. Legyen p egy prímosztója n-nek. Ekkor

(x + a)^{n} ≡ x^{n} + a (mod p, x^{r} − 1)  (6.3)

minden a-ra: 1 ≤ a ≤ A. x^{r} −1-et fel tudjuk bontani irreducibilis polinomok szorzatára a következő alakban: ∏_{d|r} Φ_{d}(x), ahol Φ_{d}(x) a d-edik körosztási polinom, aminek a gyökei a d-edik primitív egységgyökök. Minden egyes Φ_{d}(x) irreducibilis ℤ[x]-ben, de nem feltétlenül az (ℤ/pℤ)[x]-ben, ezért legyen h(x) egy irreducibilis faktora Φ_{d}(x)-nek (mod p). Ekkor 6.3-ból következik, hogy:

(x + a)^{n} ≡ x^{n} + a (mod p, h(x))  (6.4)

minden a-ra: 1 ≤ a ≤ A, mivel h(x) | x^{r} − 1.

A (mod p, h(x)) maradékosztályokat tekinthetjük az 𝔽 :≡ ℤ/(p, h(x)) gyűrű elemeinek, ami izomorf a p^{m} elemű testtel (ahol m a h polinom foka). 𝔽 nemnulla elemei p^{m} − 1 rendű ciklikus csoportot alkotnak.

6.1.1. Állítás. x primitív r-edik egységgyök 𝔽-ben.

Bizonyítás: h(x) | x^{r} −1 miatt x r-edik egységgyök (mod h(x)), ezért x rendje valamely l, amelyre l | r. Ha

x^{l} − 1 ≡ 0 (mod h(x)), és h(x) = ∏_{j=1}^{d}(x − ξ_{j}),

akkor h(x) | x^{l} − 1 miatt ξ_{j}^{l} = 1, másrészt h(x) | Φ_{r}(x) miatt ξ_{j} = ζ^{s} alkalmas s : (s, r) = 1 értékre, ahol ζ primitív r-edik egységgyök. Triviálisan igaz, hogy 1 = ξ_{j}^{l} = ζ^{s·l} nem teljesülhet, ha l < r. azaz x (mod h(x)) rendje r.

Álljon H az x, x + 1, x + 2, …, x + [A] által multiplikatívan generált elemekből (mod p, x^{r} − 1). G legyen az 𝔽 x, x + 1, x + 2, …, x + [A] által generált (ciklikus) részcsoportja; másszóval G H-nak a redukálása (mod p, h(x)).

6.1.2. Állítás. G minden eleme nemnulla.

Bizonyítás: Tegyük fel, hogy x + a = 0 𝔽-ben. Ekkor x^{n} + a = (x + a)^{n} = 0 𝔽-ben 6.4 miatt, tehát x^{n} = −a = x 𝔽-ben, amiből következne, hogy n ≡ 1 (mod r), és így d = 1, ami ellentmond a feltevésnek. Ha g(x) = ∏_{0≤a≤A}(x + a)^{e_{a}} ∈ H, akkor

g(x)^{n} = ∏_{a}((x + a)^{n})^{e_{a}} ≡ ∏_{a}(x^{n} + a)^{e_{a}} = g(x^{n}) (mod p, x^{r} − 1)

6.3 miatt. Legyen S azon pozitív egész k-k halmaza, amelyekre g(x^{k}) = g(x)^{k} (mod p, x^{r} − 1) minden g ∈ H-ra. Ekkor g(x^{k}) ≡ g(x)^{k} 𝔽-ben minden k ∈ S-re. Tudjuk, hogy p, n ∈ S.

G méretére fogunk alsó és felső becslést adni, és ebből szeretnénk ellentmondásra jutni.

Felső becslés |G|-re

6.1.3. Lemma. Ha a, b ∈ S, akkor a · b ∈ S.

Bizonyítás: Ha g(x) ∈ H, akkor g(x^{b}) ≡ g(x)^{b} (mod p, x^{r} − 1). Helyettesítsünk x helyére x^{a}-t, és így kapjuk: g((x^{a})^{b}) ≡ g(x^{a})^{b} (mod p, (x^{a})^{r} − 1), és a kongruencia teljesül (mod p, x^{r} − 1), mivel x^{r} − 1 osztja x^{a·r} − 1. Tehát

g(x)^{a·b} = (g(x)^{a})^{b} ≡ g(x^{a})^{b} ≡ g((x^{a})^{b}) = g(x^{a·b}) (mod p, x^{r} − 1),

amit bizonyítanunk kellett.

6.1.4. Lemma. Ha a, b ∈ S, és a ≡ b (mod r), akkor a ≡ b (mod |G|).

Bizonyítás: Minden g(x) ∈ ℤ[x]-re igaz, hogy u − v osztja g(u) − g(v)-t. Emiatt x^{r} − 1 osztja x^{a−b} − 1-et, ami osztja x^{a} − x^{b}-t, ami osztja g(x^{a}) − g(x^{b})-t, és így arra jutunk, hogyha g(x) ∈ H, akkor

g(x)^{a} ≡ g(x^{a}) ≡ g(x^{b}) ≡ g(x)^{b} (mod p, x^{r} − 1).

Tehát ha g(x) ∈ G, akkor g(x)^{a−b} ≡ 1 𝔽-ben; de G ciklikus csoport, ezért g-t generátornak választva kapjuk, hogy |G| osztja a − b-t.

Legyen R a (ℤ/rℤ)^{∗} n és p által generált részcsoportja. Mivel n p-nek nem hatványa, ezért az n^{i} · p^{j} egészek mind különbözőek i, j ≥ 0 esetén. Több, mint |R| különböző számot kapunk, ha 0 ≤ i, j ≤ \sqrt{|R|}, így van köztük kettő kongruens (mod r), legyen:

n^{i} · p^{j} ≡ n^{I} · p^{J} (mod r).

6.1.3 miatt mind n^{i} · p^{j}, mind n^{I} · p^{J} S-ben van, valamint 6.1.4 miatt a különbségük osztható |G|-vel, és így:

|G| ≤ |n^{i} · p^{j} − n^{I} · p^{J}| ≤ (n · p)^{\sqrt{|R|}} − 1 < n^{2\sqrt{|R|}} − 1.

(n^{i}·p^{j} −n^{I} ·p^{J} nem lehet 0, mert n nem prím, és nem is teljes hatvány.) Élesíteni fogjuk az egyenlőtlenséget azzal, hogy megmutatjuk: n/p ∈ S, és n helyébe n/p-t helyettesítve a fenti okoskodásból kapjuk:

|G| ≤ n^{\sqrt{|R|}} − 1  (6.5)

Mivel n rendje d (mod r): n^{d} ≡ 1 (mod r), és így x^{n^{d}} ≡ x (mod x^{r} − 1). Tegyük fel, hogy a ∈ S, és b ≡ a (mod n^{d} − 1). Ekkor x^{r} − 1 osztja x^{n^{d}} − x-et, ami osztja x^{b} − x^{a}-t, ami osztja g(x^{b}) − g(x^{a})-t bármely g(x) ∈ ℤ[x] esetén. Ha g(x) ∈ H, akkor g(x)^{n^{d}} ≡ g(x^{n^{d}}) (mod p, x^{r} − 1) 6.1.3 miatt, mivel n ∈ S, és g(x^{n^{d}}) ≡ g(x) (mod p, x^{r} − 1)(mivel x^{r} − 1 osztja x^{n^{d}} − x-et), és így g(x)^{n^{d}} ≡ g(x) (mod p, x^{r} − 1). De ekkor g(x)^{b} ≡ g(x)^{a} (mod p, x^{r} − 1), mivel n^{d} − 1 osztja b − a-t. Innen:

g(x^{b}) ≡ g(x^{a}) ≡ g(x)^{a} ≡ g(x)^{b} (mod p, x^{r} − 1),

mivel a ∈ S, amiből következik, hogy b ∈ S. Most legyen b = n/p és a = n · p^{φ(n^{d}−1)−1}, és így a ∈ S 6.1.3 miatt, mivel p, n ∈ S; valamint b ≡ a (mod n^{d} − 1), és így b = n/p ∈ S a fentiek miatt.

Alsó becslés |G|-re

Azt szeretnénk megmutatni, hogy sok különböző eleme van G-nek. Ha f(x), g(x) ∈ ℤ[x], és f(x) ≡ g(x) (mod p, h(x)), akkor igaz, hogy f(x)−g(x) ≡ h(x)·k(x) (mod p) valamely k(x) ∈ ℤ[x]- re. Ha f és g is alacsonyabb fokú, mint h, akkor k(x) ≡ 0 (mod p), és így f(x) ≡ g(x) (mod p). Ennélfogva a ∏_{1≤a≤A}(x + a)^{e_{a}} alakú, m-nél(h(x) foka) alacsonyabb fokú polinomok G különböző elemei. Ennek következtében ha m, p rendje (mod r), nagy, akkor jó alsó becslést tudunk adni |G|-re.

6.1.5. Lemma. Tegyük fel, hogy f(x), g(x) ∈ ℤ[x], f(x) ≡ g(x) (mod p, h(x)), és f, g egyszerüsítései 𝔽-ben G-ben vannak. Ha f és g foka alacsonyabb |R|-nél, akkor f(x) ≡ g(x) (mod p).

Bizonyítás: Legyen Δ(y) := f(y) − g(y) ∈ ℤ[x] 𝔽-beli redukálása. Ha k ∈ S, akkor:

Δ(x^{k}) = f(x^{k}) − g(x^{k}) ≡ f(x)^{k} − g(x)^{k} ≡ 0 (mod p, h(x)).

Mivel x rendje r 𝔽-ben, így {x^{k} : k ∈ R} mind különböző gyöke Δ(y)-nak (mod p, h(x)). Tehát Δ(y) foka kisebb, mint |R|, de ≥ |R| különböző gyöke van (mod p, h(x)), és így Δ(y) ≡ 0 (mod p, h(x)), amiből következik, hogy Δ(y) ≡ 0 (mod p), mivel az együtthatók függetlenek x-től.

A definíció miatt R tartalmazza az összes n által generált elemet (mod r), és így R elemeinek a száma legalább d, n rendje (mod r), ami > (log n)^{2} a feltevés miatt. Ennélfogva |R| > B, ahol B := [\sqrt{|R|} · log n]. 6.1.5-ből következik, hogy a ∏_{a∈T} (x + a) szorzatok G különböző elemei G-nek minden alkalmas T ⊂ {0, 1, 2, …, B}-re, és így:

|G| ≥ 2^{B+1} − 1 > n^{\sqrt{|R|}} − 1,

ami ellentmond 6.5-nek. Ezzel befejeztük a bizonyítást.

Megfelelő r létezése:

A prímszámtétel átfogalmazható a következő alakba: az x-nél kisebb prímek szorzata megközelítőleg e^{x}. Egy gyenge explicit változat szerint: az N és 2N közötti prímek szorzata ≥ 2^{N} N ≥ 1-re.

6.1.6. Lemma. Ha n ≥ 6, akkor létezik r ∈ [(log n)^{5}, 2(log n)^{5}] prím, amire n rendje (mod r) > (log n)^{2}

Bizonyítás:Tegyük fel indirekt, hogy nem igaz az állítás, vagyis bármely r ∈ [N, 2N], N = (log n)^{5} prímre n rendje (mod r) ≤ I := (log n)^{2}, és így a szorzatuk osztja ∏_{i≤I}(n^{i} − 1)-et. De ekkor

2^{N} ≤ ∏_{N≤r≤2Nr prím} r ≤ ∏_{i≤I}(n^{i} − 1) < n^{∑_{i≤I} i} < 2^{(log n)^{5}}

ami n ≥ 6-ra ellentmondás.

6.1.1. Az algoritmus tökéletesítése

Az eljárás gyorsítására több lehetőség is kínálkozik. Ezek lényege, hogy az r érték becslését finomítsuk. Látható, hogy ideális esetben r értéke O((log n)^{2}) nagyságrendű, így az egész algoritmus időigénye O((log n)^{6}) lehet. A következő két sejtés azt sugallja, hogy jó esély van O((log n)^{5}) nagyságrendnél kisebb r-et találni.

Az egyik az Artin-sejtés:

6.1.7. Sejtés. Legyen a ∈ ℤ nem teljes négyzet, továbbá a ≠ 0, ±1. Jelölje N_{a} azon p prímeknek a halmazát, amelyekre a a p prímszám primitív gyöke, továbbá legyen

n_{a}(x) = |{N_{a} ∩ [1, x]}|,

valamint π(x) az x-nél nem nagyobb prímek száma. Ekkor Artin sejtése szerint

lim_{n→∞} \frac{n_{a}(x)}{π(x)} = A(a),

ahol A(a) az úgynevezett Artin-konstans, az a-tól függő pozitív állandó(amelyről tudjuk, hogy A(a) > 0.35).

6.1.8. Sejtés. Azon q ≤ m prímek száma, melyekre 2q + 1 is prím, aszimptotikusan

\frac{2C_{2} · m}{(ln m)^{2}},

ahol C_{2} az úgynevezett ikerprím konstans, amelynek közelítő értéke 0.66.

Megjegyezzük, hogy utóbbi a Sophie-Germain prímek sűrűségére vonatkozó sejtésként ismeretes a szakirodalmakban.

Az Artin-sejtés igaz volta közvetlenül maga után vonná, hogy O((log n)^{2}) nagyságrendű mre található olyan r = (O(log n)^{2}), amely kielégíti a kívánt feltételeket. Sajnos jelenleg az sem bizonyított, hogy minden nem négyzetszám n esetén végtelen sok q prímszámra teljesül az o_{q}(n) = n − 1 összefüggés.

Ami a Sophie-Germain prímeket illeti, ha igaz a rájuk vonatkozó sejtés, akkor biztosan létezik legalább (log n)^{2} ilyen prím (log n)^{2} és c·(log n)^{2}·(log log n)^{2} között, megfelelő c konstans szorzóval. Minden ilyen q prímszám esetén vagy o_{q}(n) ≤ 2 áll fenn, vagy o_{q}(n) ≥ \frac{q−1}{2}. Bármely olyan q, amire o_{q}(n) ≤ 2 igaz, osztója (n − 1) · (n^{2} − 1)-nek, és így számuk O(log n) nagyságrendű. Ez a tény implikálja olyan r = Õ((log n)^{2}) létezését, ami kielégíti az o_{r}(n) ≥ 4(log n)^{2} feltételt. Egy ilyen nagyságrendű r érték az AKS-algoritmusnak Õ((log n)^{6}) futási időt eredményez.

Az időkorlát elméleti leszorítására az AKS-algoritmus szerzőinek konkrét eredménye is született. Jelölje P (m) az m legnagyobb prímosztóját. Goldfeld megmutatta, hogy pozitív valószínűséggel fordulnak elő olyan q prímek, melyekre P (q − 1) > q^{\frac{1}{2} +c}, ahol c ≈ 1/12. Ezt az eredményt Fouvry tökéletesítette, bizonyítva a következő állítást.

6.1.9. Lemma. Létezik olyan c > 0 konstans és n_{0} pozitív egész, hogy minden x ≥ n_{0} esetén:

|\{q | qprímszám, q ≤ x és P (q − 1) > q^{\frac{2}{3}} \}| ≥ c\frac{x}{ln x}.

A lemmát már igazolták 0.6683-as kitevőig. Ezen eredmények felhasználásával tudták a szerzők az AKS-algoritmus időigényét elméleti úton leszorítani.

6.1.10. Tétel. Az AKS-prímteszt algoritmus aszimptotikus időigénye Õ((log n)^{7.5}).

Bizonyítás: A fentiek értelmében az olyan q prímek, melyekre P (q − 1) > q^{\frac{2}{3}} , nagy sűrűsége azt eredményezi, hogy a 2. programrészben az eljárás talál olyan r = O((log n)^{3}) értéket, amire fennáll, hogy o_{r}(n) > 4(log n)^{2}. Emiatt lehet az algoritmusnak Õ((log n)^{7.5}) nagyságrendű futási ideje.

Biztató lehet a jövőre nézve a következő sejtés, amely ha igaz, akkor az AKS-prímteszt algoritmus aszimptotikus időigénye Õ((log n)^{3})-re módosítható. Megjegyezzük, hogy az állítás helyességét r ≤ 100 és n ≤ 10^{10} esetre már ellenőrizték.

6.1.11. Sejtés. Legyen r olyan prím, amely nem osztója n-nek. Ha fennáll az

(x − 1)^{n} ≡ x^{n} − 1 (mod x^{r} − 1, n)  (6.6)

kongruencia, akkor n prím, vagy n^{2} ≡ 1 (mod r).

Ha a sejtés igaz, akkor az a teendőnk, hogy olyan r értéket keresünk, amely nem osztója n^{2} −1nek. Ilyen r biztosan található a [2, 4 log n] intervallumban. Ez abból következik, hogy az x-nél kisebb prímek szorzata legalább e^{x}. Ezután már csak 6.6 teljesülését kell ellenőrizni, amelynek az időigénye Õ((log n)^{2}), vagyis az AKS-prímteszt futási ideje Õ((log n)^{3}).

6.2. Az algoritmus megvalósíthatósága

Az AKS-algoritmus gyakorlati megvalósításával kapcsolatban fel kell hívnunk a figyelmet egy fontos dologra. Ez nevezetesen az, hogy bonyolultságelméleti szempontból a futásidő nagyon kedvezően alakul, viszont a tárigény olyan mértékűnek mutatkozik, ami viszonylag kicsi számoknál is óriási operatív memóriát feltételez. A gyorsaság érdekében az egy lépésben vizsgált polinom együtthatóit mind az operatív tárban célszerű tartani.

Egy (x + a)^{n} − x^{n} − a alakú polinom osztási maradéka a (mod x^{r} − 1, n) modulus szerint egy legfeljebb (r − 2)-edfokú polinom lesz, amelynek együtthatói legfeljebb az n − 1 értéket vehetik fel. Tehát legrosszabb esetben (r−1) darab együtthatót kell ellenőriznünk, amelyek tárigénye akár (r− 1)·⌈log(n−1)⌉ bit is lehet. Legyen n a legnagyobb 1000 decimális számjegyű pozitív egész. Tegyük fel, hogy r értéke eléri a bizonyításban szereplő ⌈2(log n)^{5}⌉ korlátot. Ekkor egyszerű számolással belátható, hogy a tárigény túllépheti a 3·10^{14} gigabájtot. Manapság egy 1000 számjegyű egész szám nem számít nagynak prímtesztelés szempontjából, de ekkora operatív tár nem áll rendelkezésre.

Érdemes elvégezni ugyanezt a számolást úgy, hogy feltesszük, hogy a 6.1.11 sejtés igaz. Ekkor találunk olyan r-et, amelyre r ≤ 4(log n), ami azt jelenti, hogy a tárigény 5,27 gigabájt alá csökken.

A fenti számítások azt támasztják alá, hogy nem kell teljesen elfelejteni gyakorlati alkalmazások szempontjából az AKS-prímteszt eljárást, viszont ahhoz, hogy valóban egy determinisztikus, nagy számok prímtesztelésére is alkalmas számítógépes program születhessen, még szükség van új matematikai eredményekre, elsődlegesen a 6.1.11 sejtés bizonyítására gondolunk, a hardverek fejlődésére, valamint ügyes programozói megoldásokra.

6.3. Lenstra és Pomerance változata

Lenstra és Pomerance jelentősen megváltoztatta az AKS-algoritmust, aminek így Õ((log n)^{6}) lett a műveletigénye. A kulcsötletük a Φ_{r}(x) polinom kicserélése egy bizonyos tulajdonságokkal rendelkező f(x) polinomra.

Adott f(x) egészegyütthatós, 1 főegyütthatós d-edfokú polinom és n pozitív egész szám esetén azt mondjuk, hogy ℤ[x]/(n, f(x)) pszeudotest, ha

1. f(x^{n}) ≡ 0 (mod n, f(x)),

2. x^{n^{d}} − x ≡ 0 (mod n, f(x)), és

3. x^{n^{d/q}} − x egység ℤ[x]/(n, f(x)) minden prím q-ra, ami osztja d-t

Ha n prím, és f(x) irreducibilis (mod n), akkor teljesülnek ezek a feltételek, és ℤ[x]/(n, f(x)) test.

Adott n > 2 egész számhoz legyen d ∈ ((log n)^{2}, n) olyan egész, amire létezik az f(x) egészegyütthatós, 1 főegyütthatós d-edfokú polinom úgy, hogy ℤ[x]/(n, f(x)) pszeudotest. Ekkor n prím akkor és csak akkor, ha

• n nem teljes hatvány

• n-nek nincs olyan prímosztója, ami ≤ d

• (x + a)^{n} ≡ x^{n} + a (mod n, f(x)) minden a egész számra, amire 1 ≤ a ≤ A := \sqrt{d} · log n

Ránézésre látszik, hogy ez a tétel Agrawal, Kayal és Saxena munkájából gyökerezik, de már általánosabb. Ebből az általánosságból adódik, hogy sokkal kevesebb lépést igényel.

Nyilvánvaló, hogy adott f-re gyorsan meg lehet határozni, hogy pszeudotestet kapunk-e, és ha igen, akkor teljesülnek-e a feltételek. Ennélfogva ha gyorsan tudunk találni olyan f-et, ami pszeudotestet ad, akkor ez a megközelítés egy gyors prímteszthez vezet. f megkonstruálása Lenstra és Pomerance által Gausshoz nyúlik vissza, a szabályos n-szögek szerkesztéséhez, ahhoz a témához amit manapság Gauss-periódusokként ismerünk.

A karakterizáció bizonyítása:

Tegyük fel, hogy n összetett és teljesíti a három feltevést. Legyen p n egy prímosztója, és h(x) f(x) irreducibilis faktora (mod p), és így 𝔽 ≡ ℤ[x]/(p, h(x)) izomorf egy véges testtel.

Ahogy a 6.1 részben is , álljon H (mod p, f(x)) azon elemeiből amelyeket x, x+1, x+2, …, x+[A] multiplikatívín generálnak; legyen G 𝔽 azon részcsoportja, amit x, x+1, x+2, …, x+[A] generálnak; és legyen S a p^{i} · n^{j}, i, j ≥ 0 alakú pozitív egészek halmaza. Definiáljuk r-et, mint x rendje (mod p, f(x)), így d lesz n rendje (mod r) (2) és (3) miatt, és x^{n^{0}}, x^{n^{1}}, …, x^{n^{d−1}} különbözőek (mod p, f(x)), sőt különbözőek (mod p, h(x)) is. Ennélfogva a g(T) := ∏_{i=0}^{d−1}(T − x^{n^{i}}) ∈ 𝔽[T] polinom gyökei különbözőek; továbbá g(x^{p}) = g(x)^{p} = 0 𝔽-ben, ezért x^{p}-nek egyenlőnek kell lennie x^{n^{j}}-nel 𝔽-ben valamely j-re. Ebből következik, hogy p ≡ n^{j} (mod r), és ezért ha R (ℤ/rℤ)^{∗}-nak n és p által generált részcsoportja, akkor R-et n egyedül is generálja, és R-nek d eleme van.

A 6.1 részben leírt bizonyítás működik a 6.1.3 lemmára, leszámítva azt az észrevételt miszerint x^{r} − 1 osztja x^{k·r} − 1-et bármely k ∈ S-re. Ezt lecseréljük arra a tényre, hogy f(x^{k}) ≡ 0 (mod p, f(x)) minden k ∈ S-re, ami azért áll fenn, mert f(x^{n}) ≡ 0 (mod p, f(x)) (1) miatt, és f(x^{p}) ≡ f(x)^{p} (mod p) ≡ 0 (mod p, f(x)) a "gyerekek binomiális tétele" miatt.

A 6.1.4 lemma adódik nagyon hasonló bizonyítással((p, x^{r} − 1)-et cseréljük (p, f(x))-re), mivel (p, f(x)) osztja (p, x^{r} − 1)-et. A 6.5 utáni megjegyzések egyszerűen következnek, ha az ottani első mondatot lecseréljük (2)-re, és a továbbiakban (p, x^{r} − 1) helyére (p, f(x))-et írjuk. Ennélfogva 6.5 és 6.1.5 lemma fennáll, ezért ugyanúgy, mint a 6.1 részben |G| ≥ 2^{B+1} − 1, ahol B := [A], és így |G| > n^{\sqrt{|R|}} − 1 ami ellentmondásban van 6.5-tel.

f megkonstruálása:

Legyen ζ_{r} = e^{2πi/r} prím r-re. Ha q osztja r − 1-re, definiáljuk a Gauss-periódust a következőképpen: η = ∑_{j∈J} ζ_{r}^{j}, ahol J = J_{r,q} = {j (mod r) : j^{(r−1)/q} ≡ 1 (mod r)} azon maradékosztályok halmaza (mod r), amelyek relatív prímek r-hez, és q-adik hatványok (mod r). J részcsoportja a (ℤ/rℤ)^{∗} ciklikus csoportnak, és így J = {g^{q·i} : 0 ≤ i ≤ (r−1)/q} (ℤ/rℤ)^{∗} g generátorára. Továbbá J-nek q darab mellékosztálya van (ℤ/rℤ)^{∗}-ban, ezek g^{i} · J, ahol 0 ≤ i ≤ q − 1. Így η = η_{0} konjugáltjai: η_{i} := ∑_{j∈J} ζ_{r}^{g^{i}·j}, i = 0, 1, 2, …, q − 1. η ℚ fölötti minimálpolinomja: f(x) = ∏_{i=0}^{q−1}(x − η_{i}), ami egészegyütthatós 1 főegyütthatós q-adfokú polinom.

Legyen p r-től különböző prímszám. A ℚ(ζ_{r}) testben a ℚ fölötti prímek(mint például p) esetleg továbbbonthatóak prímideálokra, ezért tegyük fel, hogy P p egy prímideálfaktora ℚ(ζ_{r})-ben. Elképzelhető, hogy f(x) is felbontható (mod p), így legyen g(x) f(x) azon faktora (mod p), amelyre g(η) ≡ 0 (mod P). A "gyerekek binomiális tétele" szerint g(x^{p}) ≡ g(x)^{p} (mod p), és így (mod P) is, ennélfogva g(η^{p}) ≡ g(η)^{p} ≡ 0 (mod P). Innen η^{p} ≡ η_{k} (mod p), ahol η_{k} ∈ g^{k} · J gyöke g(x)-nek (mod P), és hasonló okoskodással azt kapjuk, hogy η_{ik (mod q)} is az i = 0, 1, …, q − 1-re. Ezek pontosan akkor különbözőek, ha p^{(r−1)/q} rendje (mod r) éppen q. Ebből arra következtethetünk, hogy f(x) pontosan akkor irreducibilis (mod p), ha p^{(r−1)/q} rendje (mod r) éppen q.

Ilymódon tudunk konstruálni egy q-adfokú irreducibilis polinomot 𝔽_{p} fölött, az η Gauss-periódus minimálpolinomját. Továbbá, ha van néhány prímünk: r_{1}, r_{2}, …, r_{k}, és páronként relatív prím pozitív egész számunk: q_{1}, q_{2}, …, q_{k}, amelyekre igaz, hogy q_{i} osztja r_{i} − 1-et minden egyes i-re, akkor f(x): η_{1} · η_{2} ⋯ η_{k} minimálpolinomja ℚ fölött q_{1} · q_{2} ⋯ q_{k}-adfokú, és irreducibilis (mod p) pontosan akkor, ha p^{(r_{i}−1)/q_{i}} rendje (mod r) éppen q_{i} minden egyes i-re. Ez a gondolat elvezet f megkonstruálásához: adott n-re keressünk q_{i}-t és r_{i}-t mint fönt, p-t n-re cserélve. Ha n prím, akkor ℤ[x]/(n, f(x)) pszeudotest. Ha n összetett, akkor ℤ[x]/(n, f(x)) vagy nem pszeudotest, és ebben az esetben bizonyítékunk van arra, hogy n összetett; vagy az, és ekkor alkalmazhatjuk Lenstra és Pomerance tételét, feltéve hogy q_{1}q_{2} ⋯ q_{k} > (log n)^{2} n tesztelésére. Valójában ők bebizonyították, hogy létezik ilyen f q_{1}q_{2} ⋯ q_{k}-val, ami nem sokkal nagyobb (log n)^{2}-nél:

Feladat: Létezik n_{0} konstans, amelyre n ≥ n_{0} esetén léteznek r_{1}, r_{2}, …, r_{k} < (log n)^{2} prímek és q_{1}, q_{2}, …, q_{k} páronként relatív prím pozitív egészek, amelyekre q_{i} osztja r_{i} − 1-et, és n^{(r_{i}−1)/q_{i}} rendje (mod r) éppen q_{i} minden egyes i-re úgy, hogy (log n)^{2} < q_{1}q_{2} ⋯ q_{k} < 4(log n)^{2}.

Annak meghatározásához, hogy n^{(r_{i}−1)/q_{i}} rendje (mod r) éppen q_{i}-e csak azt kell ellenőriznünk, hogy n^{r_{i}−1} ≡ 1 (mod r_{i}) teljesül-e, miközben n^{(r_{i}−1)/q} ≡ 1 (mod r_{i}). A fenti feladatot felhasználva egyszerűen meg tudunk határozni megfelelő r_{i} és q_{i} értékeket O((log n)^{3}) lépésben.

Irodalomjegyzék

[1] Farkas Gábor, Kátai Imre: Informatikai algoritmusok 2. Számelmélet című része [2] Andrew Granville: It Is Easy to Determine Whether a Given Integer Is Prime [3] David M. Bressoud: Factorization and Primality Testing

[4] Victor Shoup: A Computational Introduction to Number Theory and Algebra [5] Járai Antal: Számítógépes számelmélet