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

A Wikipédiából, a szabad enciklopédiából
[ellenőrzött változat][ellenőrzött változat]
Tartalom törölve Tartalom hozzáadva
SamatBot (vitalap | szerkesztései)
a három pont --> hárompont
SamatBot (vitalap | szerkesztései)
a →‎Álprímek: kisebb formai javítások,
32. sor: 32. sor:


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
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
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ő.
''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
3. Ha ''n'' csak egyetlen hozzá relatív prím ''t'' -re is bukja a
54. sor: 54. sor:
'''Állítás''' - ''n'' bukja a tesztet ezekre a ''tb''<sub>1</sub><''tb''<sub>2</sub>< … <''tb''<sub>''k''</sub> számokra.
'''Á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.
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==
==A Carmichael-számok karakterizációja==

A lap 2010. január 13., 02:31-kori változata

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 ap-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. Euklidészi 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 an-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 × log2n × 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

bi Ha n összetett, és an-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 kevés.

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(b1,n)=lnko(b2,n)=1. Ha n álprím a b1 és a \b2 alapra nézve, akkor álprím a \b1b2, és a b1b2−1 alapokra is, ahol b2−1 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 bn-1=b(kd)=(bd)k kongruens 1k=1 mod n.

Vizsgáljuk most a redukált mod n maradékosztályokat. Ha ebben a csoportban valamely elemre igaz az, hogy an-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 (b1)d(b2)d=(b1b2)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 b1<b2< … <bk 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 b1<b2< … <bk számokat, ezek páronként inkongruensek lesznek.

Állítás - n bukja a tesztet ezekre a tb1<tb2< … <tbk számokra.

Tegyük fel indirekt, hogy tbi -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 tbibi−1 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 teljesülnek rá a következők:

1. n négyzetmentes

2. Minden p prímosztójára p-1 osztója n-1 -nek.

Bizonyítás

1. Tegyük fel, hogy p2 osztója n -nek. Belátjuk, hogy n nem lehet Carmichael-szám.

Mivel n páratlan, azért p>2. Vegyünk egy g primitív gyököt p2. Legyen m a legnagyobb olyan osztója n -nek, ami négyzetmentes, és nem osztható p -vel. Tekintsük a következő kongruenciarendszert:

b kongruens g mod p^2

b kongruens 1 mod m

Ez megoldható, mert m és p^2 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) kongruens 1 mod n. Ekkor a kongruencia p2 -re is teljesül, hiszen p2 osztója n -nek. b mod p2 rendje osztója n-1 -nek, de b primitív gyök mod p2. 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) kongruens 1 mod p. Mivel p osztója n -nek, azért b(n-1) kongruens 1 mod p fennáll minden b relatív prímre és p prímosztóra. Tekintsük a következő kongruenciarendszert:

b kongruens g mod p

b kongruens 1 mod m,

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

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

Következik, hogy bn-1 kongruens gn-1 mod p. Ez teljesül, ha p-1 osztója n-1 -nek, ugyanis g rendje p-1 mod p, és éppen ez az állítás. Különben b(n-1) nem kongruens 1 mod p, így bp-1 nem kongruens 1 mod 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.