Fermat-prímteszt

A Fermat-prímteszt (vagy Fermat-féle prímszámpróba) egy valószínűségi prímteszt. A kis Fermat-tételen alapul, ami kimondja, hogy ha p prím, akkor a^p-1 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 algoritmussal ellenőrizhető, hogy n és a relatív prímek. Ha nem azok, akkor n bukja a tesztet, ö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.

Futási ideje moduláris hatványozással O(k × log²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_i 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.

Legyen most n páratlan pozitív egész. Teljesül a következő

Tétel:

1. n akkor és csak akkor álprím a b alapra, ha a mod n maradékosztályok csoportjában b 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.

Bizonyítás:

1. Ha b d rendje osztója n-1-nek, akkor bn-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.

Vizsgáljuk most a redukált mod n maradékosztályokat. Ha ebben a csoportban valamely elemre igaz az, hogy a^n-1 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₁)^d(b₂)^d=(b₁b₂)^d (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₁<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.

Állítás - n bukja a tesztet ezekre a tb₁<tb₂< … <tb_k számokra.

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ékosztályok csoportjában n a tb_ib_i⁻¹ maradékosztály minden elemére álprím, így a t számra is, ami ellentmondás.

A Carmichael-számok karakterizációja

Tétel: Legyen n páratlan összetett szám. n akkor és csak akkor Carmichael-szám, ha:

1. n négyzetmentes és

2. n minden p prímosztójára $p-1|n-1$.

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 $p^{2}|n$.

Mivel n páratlan, azért p>2. Vegyünk egy g primitív gyököt 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:

$b\equiv g{\pmod {p^{2}}}$

$b\equiv 1{\pmod {m}}$.

Ez a kongruenciarendszer megoldható, mert m és p² relatív prímek. Vegyük a kongruenciarendszer egy b megoldását.

Állítás - n bukja a tesztet a b alapra nézve.

Tegyük fel indirekt, hogy $b^{n-1}\equiv 1{\pmod {n}}$.

Ekkor a kongruencia p²-re is teljesül, hiszen $p^{2}|n$. 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

$b^{p-1}\equiv 1{\pmod {p}}$.

Mivel $p|n$, ezért minden b relatív prímre és p prímosztóra:

$b^{n-1}\equiv 1{\pmod {p}}$ .

Tekintsük a következő kongruenciarendszert:

$b\equiv g{\pmod {p}}$

$b\equiv 1{\pmod {m}}$,

ahol m=n/p, és g primitív gyök mod p.

Ez megoldható, mert m és p² relatív prímek. Vegyük a kongruenciarendszer egy b megoldását.

Következik, hogy

$b^{n-1}\equiv g^{n-1}{\pmod {p}}$.

Ez teljesül, ha $p-1|n-1$, ugyanis g rendje p-1 mod p, és éppen ez az állítás. Különben

$b^{n-1}\not \equiv 1{\pmod {p}}$, így

$b^{p-1}\not \equiv 1{\pmod {n}}$.

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.