„Fermat-prímteszt” változatai közötti eltérés

nincs szerkesztési összefoglaló
A '''Fermat-prímteszt''' (vagy Fermat-féle prímszámpróba) egy valószínűségi prímteszt. A [[kis Fermat-tétel]]en alapul, ami kimondja, hogy ha ''p'' [[Prímszámok|prím]], akkor ''a''<sup>''p''-1</sup> [[kongruencia|kongruens]] ''1'' mod ''p'', ha ''p'' nem osztója ''a''-nak.
''a''<sup>''p''-1</sup> [[kongruencia|kongruens]] ''1'' mod ''p'', ha ''p'' nem osztója ''a''-nak.
 
==Menete==
 
Meg kívánjuk vizsgálni, hogy ''n'' szám ''1''-nél nagyobb páratlan egész prím-e. Legyen ''1<a<n''. [[Euklideszi algoritmus]]sal ellenőrizhető, hogy ''n'' és ''a'' [[relatív prímek]]. Ha nem azok, akkor ''n'' bukja a tesztet, [[összetett számok|összetett]].
''1<a<n''. [[Euklideszi algoritmus]]sal ellenőrizhető, hogy ''n'' és ''a'' [[relatív prímek]]. Ha nem azok, akkor ''n'' bukja a tesztet, [[összetett számok|összetett]].
 
Ha ''n'' prím, akkor ''a''<sup>''n''-1</sup> kongruens ''1 mod n''. Ha nem így van, akkor ''n'' bukja a tesztet, összetett. Ha igen, akkor újabb véletlen ''a''-val folytatódik a vizsgálat, egészen addig, amíg eléggé biztossá nem válik, hogy n valószínűleg prím. A legtöbb összetett szám ugyanis legfeljebb ''1/2'' valószínűséggel állja a tesztet egy véletlen ''a''-ra.
bukja a tesztet, összetett. Ha igen, akkor újabb véletlen ''a'' -val
folytatódik a vizsgálat, egészen addig, amíg eléggé biztossá nem
válik, hogy n valószínűleg prím. A legtöbb összetett szám ugyanis
legfeljebb ''1/2'' valószínűséggel állja a tesztet egy véletlen ''a'' -ra.
 
Futási ideje moduláris hatványozással O(''k'' × log<sup>2</sup>''n'' × log log ''n'' × log log log ''n''), ahol ''k'' a fordulók száma, azaz ennyi véletlen alapra megy a tesztelés.
==Álprímek==
b<sub>i</sub>
Ha ''n'' összetett, és ''a''<sup>''n''-1</sup> ''kongruens 1 mod n'' valamely ''a'' -ra, akkor ''n a'' alapú '''álprím''', másként '''pszeudoprím'''. Ilyen például a ''341'', ami álprím a ''2'' alapra.
alapú '''álprím''', másként '''pszeudoprím'''. Ilyen például a ''341'', ami álprím a ''2'' alapra.
 
Ha a kongruencia minden, az ''n'' -hez relatív prím ''a'' -ra fennáll, akkor ''n'' '''univerzális álprím''', más néven '''Carmichael-szám'''. A legkisebb ilyen szám az ''561''. Végtelen sok ilyen szám van, de viszonylag ritkán.
'''univerzális álprím''', más néven '''Carmichael-szám'''. A legkisebb ilyen szám az ''561''.
Végtelen sok ilyen szám van, de viszonylag ritkán.
 
Legyen most ''n'' páratlan pozitív egész. Teljesül a következő
'''Tétel:'''
 
1. ''n'' [[bikondicionális|akkor és csak akkor]] álprím a ''b'' alapra, ha a ''mod n'' maradékosztályok csoportjában ''b'' [[multiplikatív rend|rendje]] osztója ''n-1''-nek.
maradékosztályok csoportjában ''b'' [[multiplikatív rend|rendje]] osztója ''n-1'' -nek.
 
2. Legyen ''lnko(b<sub>1</sub>,n)=lnko(b<sub>2</sub>,n)=1''. Ha ''n'' álprím a ''b''<sub>1</sub> és a \''b''<sub>2</sub> alapra nézve, akkor álprím a \''b''<sub>1</sub>''b''<sub>2</sub>, és a ''b''<sub>1</sub>''b''<sub>2</sub><sup>−1</sup> alapokra is, ahol ''b''<sub>2</sub><sup>−1</sup> a redukált mod n maradékosztályok csoportján értendő.
nézve, akkor álprím a \''b''<sub>1</sub>''b''<sub>2</sub>, és a ''b''<sub>1</sub>''b''<sub>2</sub><sup>−1</sup> alapokra is, ahol
''b''<sub>2</sub><sup>−1</sup> a redukált mod n maradékosztályok csoportján értendő.
 
3. Ha ''n'' csak egyetlen hozzá relatív prím ''t'' -re is bukja a Fermat-tesztet, akkor a redukált maradékosztályoknak legalább a felére bukja.
Fermat-tesztet, akkor a redukált maradékosztályoknak legalább a felére
bukja.
 
'''Bizonyítás:'''
 
1. Ha ''b d'' rendje osztója ''n-1'' -nek, akkor ''b<sup>''n''-1</sup> kongruens 1 mod n'', mert akkor ''n-1=kd'' valamely egész ''k'' -ra, így ''b''<sup>''n''-1</sup>=''b<sup>(kd)</sup>=(b<sup>d)<sup>k</sup></sup> kongruens 1<sup>k</sup>=1 mod n''.
 
Vizsgáljuk most a redukált ''mod n'' maradékosztályokat. Ha ebben a csoportban valamely elemre igaz az, hogy ''a''<sup>''n''-1</sup> kongruens ''1 mod n'', és egy másik ''k'' kitevőre is kongruens ''1 mod n'', akkor ''a''^(n-1-k)
kongruens ''1 mod n'' is teljesül. Így le lehet folytatni az euklideszi algoritmust, és kiderül, hogy ''d=lnko(n-1,k)'' -ra is igaz, hogy ''a^d'' kongruens ''1 mod n''. Tehát van egy ''d'' osztója ''n-1'' -nek, amire a kongruencia teljesül.
 
Ha a legkisebb ilyen ''k'' -t vesszük, akkor ez az előzőek szerint osztója lesz ''n-1'' -nek, mert ha nem lenne meg maradéktalanul benne, akkor az a maradék kisebb lenne. Ez a legkisebb ''k'' kitevő pedig definíció szerint ''a'' maradékosztályának rendje a redukált maradékosztályok csoportjában.
 
2. Az kell, hogy az ilyen redukált maradékosztályok csoportot alkotnak. Ez így van, mert egyrészt (''b''<sub>1</sub>)<sup>''d''</sup>(''b''<sub>2</sub>)<sup>''d''</sup>=(''b''<sub>1</sub>''b''<sub>2</sub>)<sup>''d''</sup> (merthogy a redukált maradékosztályok csoportja kommutatív). Másrészt, ha ''b'' rendje ''d'', akkor inverzének rendje is ''d''
 
3. Legyenek most ''b''<sub>1</sub><''b''<sub>2</sub>< … <''b''<sub>''k''</sub> páronként inkongruens alapok, amelyekre n álprím. Most tekintsünk egy olyan ''n'' -hez relatív prím ''t'' -t, amelyre ''n'' bukja a tesztet. Szorozzuk meg vele az előbbi ''b''<sub>1</sub><''b''<sub>2</sub>< … <''b''<sub>''k''</sub> számokat, ezek páronként inkongruensek lesznek.
 
'''''Állítás''''' - ''n'' bukja a tesztet ezekre a ''tb''<sub>1</sub><''tb''<sub>2</sub>< … <''tb''<sub>''k''</sub> számokra.
 
Tegyük fel indirekt, hogy ''tb''<sub>''i''</sub> -re nem bukja a tesztet, azaz ''n'' álprím erre az alapra. Ekkor ''mod n'' számolva a [[redukált maradékrendszer|redukált maradékosztályok]] csoportjában ''n'' a ''tb''<sub>''i''</sub>''b''<sub>''i''</sub><sup>−1</sup> maradékosztály minden elemére álprím, így a ''t'' számra is, ami ellentmondás.
 
==A Carmichael-számok karakterizációja==
1. n [[négyzetmentes szám|négyzetmentes]] és
 
2. n minden ''p'' prímosztójára <math>p-1|n-1</math>.
 
'''Bizonyítás'''
 
1. Tegyük fel, hogy ''n'' nem négyzetmentes. Belátjuk, hogy ''n'' nem lehet Carmichael-szám.
Mivel ''n'' nem négyzetmentes, van olyan ''p'' prímszám, hogy <math>p^2| n</math>.
 
Mivel ''n'' páratlan, azért ''p>2''. Vegyünk egy ''g'' [[Primitív_gyök|primitív gyökötgyök]]öt modulómodulo ''p''<sup>2</sup>. Legyen ''m'' a legnagyobb olyan osztója ''n'' -nek, ami négyzetmentes, és nem osztható ''p'' -vel. Tekintsük a következő kongruenciarendszert:
 
:<math> b \equiv g \pmod{p^2}</math>
'''''Állítás''''' - ''n'' bukja a tesztet a ''b'' alapra nézve.
 
Tegyük fel indirekt, hogy <math>b^{n-1}\equiv 1\pmod{n}</math>.
 
Ekkor a kongruencia ''p''<sup>2</sup> -re is teljesül, hiszen <math>p^2 |n</math>. ''b mod p<sup>2</sup>'' rendje osztója ''n-1'' -nek, de ''b'' primitív gyök ''mod p<sup>2</sup>''. Ezért ''p-1'' és ''p'' is osztója ''n-1'' -nek, és ez ellentmondás, mert két szomszédos egész szám mindig relatív prím egymáshoz.
 
2. Legyen most ''n'' páratlan, összetett és négyzetmentes. Ha most ''b'' relatív prím ''n'' -hez, akkor a Fermat-tétel szerint teljesül
:<math>b^{p-1}\equiv 1\pmod{p}</math>.
Mivel <math>p|n</math>, ezért minden ''b'' relatív prímre és ''p'' prímosztóra:
:<math>b^{n-1}\equiv 1\pmod{p}</math> .
Tekintsük a következő kongruenciarendszert:
 
:<math> b \equiv g \pmod{p}</math>
:<math> b \equiv 1 \pmod{m}</math>,
 
Ez megoldható, mert ''m'' és ''p''<sup>2</sup> relatív prímek. Vegyük a kongruenciarendszer egy ''b'' megoldását.
 
Következik, hogy
:<math> b^{n-1} \equiv g^{n-1} \pmod{p}</math>.
Ez teljesül, ha <math>p-1|n-1</math>, ugyanis ''g'' rendje ''p-1 mod p'', és éppen ez az állítás. Különben
:<math> b^{n-1}\not\equiv 1 \pmod{p}</math>, így
:<math> b^{p-1}\not\equiv 1 \pmod{n}</math>.
 
 
 
==Források==
*N. Koblitz: A Course in Number Theory and Cryptography 1994
*Freud Róbert -, Gyarmati Edit: Számelmélet
*Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 889–890 of section 31.8, Primality testing.