„Fermat-prímteszt” változatai közötti eltérés
[nem ellenőrzött változat] | [nem ellenőrzött változat] |
→A Carmichael-számok karakterizációja: 2. bizonyításának befejezése |
a jelölés |
||
7. sor: | 7. sor: | ||
''1<a<n''. [[Euklidészi algoritmus]]sal ellenőrizhető, hogy ''n'' és ''a'' [[relatív prímek]]. Ha nem azok, akkor ''n'' bukja a tesztet, [[összetett szám|összetett]]. |
''1<a<n''. [[Euklidészi algoritmus]]sal ellenőrizhető, hogy ''n'' és ''a'' [[relatív prímek]]. Ha nem azok, akkor ''n'' bukja a tesztet, [[összetett szám|összetett]]. |
||
Ha ''n'' prím, akkor ''a |
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 |
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 |
folytatódik a vizsgálat, egészen addig, amíg eléggé biztossá nem |
||
15. sor: | 15. sor: | ||
==Álprímek== |
==Álprímek== |
||
Ha ''n'' összetett, és ''a |
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. |
||
30. sor: | 30. sor: | ||
2. Legyen ''lnko(b_1,n)=lnko(b_2,n)=1''. Ha ''n'' álprím a ''b_1 ''és a ''b_2'' alapra |
2. Legyen ''lnko(b_1,n)=lnko(b_2,n)=1''. Ha ''n'' álprím a ''b_1 ''és a ''b_2'' alapra |
||
nézve, akkor álprím a ''b_1b_2'', és a ''b_1b_2 |
nézve, akkor álprím a ''b_1b_2'', és a \''b_1b_2''<sup>-1</sup> alapokra is, ahol |
||
''b_2 |
\''b_2''<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 |
||
39. sor: | 39. sor: | ||
'''Bizonyítás:''' |
'''Bizonyítás:''' |
||
1. Ha ''b d'' rendje osztója ''n-1'' -nek, akkor ''b |
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 |
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''<sup>n-1-k<\sup> 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. |
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_1) |
2. Az kell, hogy az ilyen redukált maradékosztályok csoportot alkotnak. Ez így van, mert egyrészt \''(b_1)<sup>d</sup>(b_2)<sup>d</sup>=(b_1b_2)<sup>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_1<b_2< ... <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_1<b_2< ... <b_k'' számokat, ezek páronként inkongruensek lesznek. |
3. Legyenek most ''b_1<b_2< ... <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_1<b_2< ... <b_k'' számokat, ezek páronként inkongruensek lesznek. |
||
51. sor: | 51. sor: | ||
'''Állítás''' - ''n'' bukja a tesztet ezekre a ''tb_1<tb_2< ... <tb_k'' számokra. |
'''Állítás''' - ''n'' bukja a tesztet ezekre a ''tb_1<tb_2< ... <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ály]]ok csoportjában ''n'' a ''tb_ib_i |
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ály]]ok csoportjában ''n'' a \''tb_ib_i''<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== |
||
64. sor: | 64. sor: | ||
'''Bizonyítás''' |
'''Bizonyítás''' |
||
1. Tegyük fel, hogy ''p |
1. Tegyük fel, hogy \''p''<sup>2</sup> 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 '' |
Mivel ''n'' páratlan, azért ''p>2''. Vegyünk egy ''g'' primitív gyököt \''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: |
||
''b kongruens g mod p^2'' |
''b kongruens g mod p^2'' |
||
76. sor: | 76. sor: | ||
'''Állítás''' - ''n'' bukja a tesztet a ''b'' alapra nézve. |
'''Állítás''' - ''n'' bukja a tesztet a ''b'' alapra nézve. |
||
Tegyük fel indirekt, hogy ''b |
Tegyük fel indirekt, hogy \''b''<sup>(''n''-1)</sup> ''kongruens 1 mod n''. Ekkor a kongruencia \''p''<sup>2</sup> -re is teljesül, hiszen \''p<sup>2</sup>'' osztója ''n'' -nek. \''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 ''b |
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''<sup>(''p''-1)</sup> ''kongruens 1 mod p''. Mivel ''p'' osztója ''n'' -nek, azért \''b''<sup>(''n''-1)</sup> 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 g mod p'' |
||
86. sor: | 86. sor: | ||
ahol ''m=n/p'', és ''g'' primitív gyök ''mod p'' |
ahol ''m=n/p'', és ''g'' primitív gyök ''mod p'' |
||
Ez megoldható, mert ''m'' és ''p |
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 ''b |
Következik, hogy \''b''<sup>''n''-1</sup> ''kongruens g''<sup>''n''-1</sup> ''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<sup>(n-1)</sup> nem kongruens 1 mod p'', így \''b''<sup>''p''-1</sup> ''nem kongruens 1 mod n'' |
||
[[Kategória:Számelmélet]] |
[[Kategória:Számelmélet]] |
||
A lap 2008. július 14., 20: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.
Álprímek
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(b_1,n)=lnko(b_2,n)=1. Ha n álprím a b_1 és a b_2 alapra nézve, akkor álprím a b_1b_2, és a \b_1b_2-1 alapokra is, ahol \b_2-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 \b(n-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 \an-1-k<\sup> 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_1)d(b_2)d=(b_1b_2)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_1<b_2< ... <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_1<b_2< ... <b_k számokat, ezek páronként inkongruensek lesznek.
Állítás - n bukja a tesztet ezekre a tb_1<tb_2< ... <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-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