„Fermat-prímteszt” változatai közötti eltérés
[nem ellenőrzött változat] | [nem ellenőrzött változat] |
→Álprímek: A Carmichael-számok karakterizációja |
→Álprímek: 1. bionyításának folytatása |
||
40. sor: | 40. sor: | ||
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''. |
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''. |
||
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 euklidészi 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. |
|||
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'' |
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'' |
A lap 2008. július 13., 21:08-kori változata
A Fermat-prímteszt 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
Legyen a tesztelendő n szám 1-nél nagyobb páratlan egész, és 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 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.
Álprímek
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 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 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.
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 euklidészi 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.
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ét 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.
Források
- N. Koblitz: A Course in Number Theory and Cryptography 1994
- Freud Róbert - Gyarmati Edit: Számelmélet