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

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''^''p''-1 [[kongruencia|kongruens]] ''1'' mod ''p'', ha ''p'' nem osztója ''a''-nak.

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]].

Ha ''n'' prím, akkor ''a''^''n''-1 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.

Ha ''n'' összetett, és ''a''^''n''-1 ''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.

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.

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.

2. Legyen ''lnko(b₁,n)=lnko(b₂,n)=1''. Ha ''n'' álprím a ''b''₁ és a \''b''₂ alapra nézve, akkor álprím a \''b''₁''b''₂, és a ''b''₁''b''₂⁻¹ alapokra is, ahol ''b''₂⁻¹ 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.

1. Ha ''b d'' rendje osztója ''n-1'' -nek, akkor ''b^''n''-1 kongruens 1 mod n'', mert akkor ''n-1=kd'' valamely egész ''k'' -ra, így ''b''^''n''-1=''b^(kd)=(b^{d)^k} kongruens 1^k=1 mod n''.

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.

3. Legyenek most ''b''₁<''b''₂< … <''b''_''k'' 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''₁<''b''₂< … <''b''_''k'' számokat, ezek páronként inkongruensek lesznek.

Tegyük fel indirekt, hogy ''tb''_''i'' -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''_''i''''b''_''i''⁻¹ maradékosztály minden elemére álprím, így a ''t'' számra is, ami ellentmondás.

2. n minden ''p'' prímosztójára <math>p-1|n-1</math>.

'''Bizonyítás'''

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''². Legyen ''m'' a legnagyobb olyan osztója ''n'' -nek, ami négyzetmentes, és nem osztható ''p'' -vel. Tekintsük a következő kongruenciarendszert:

Tegyük fel indirekt, hogy <math>b^{n-1}\equiv 1\pmod{n}</math>.

Ekkor a kongruencia ''p''² -re is teljesül, hiszen <math>p^2 |n</math>. ''b mod p²'' rendje osztója ''n-1'' -nek, de ''b'' primitív gyök ''mod p²''. 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>.

:<math>b^{n-1}\equiv 1\pmod{p}</math> .

:<math> b \equiv g \pmod{p}</math>

Következik, hogy

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>.

*Freud Róbert -, Gyarmati Edit: Számelmélet