„Fermat-prímteszt” változatai közötti eltérés
[nem ellenőrzött változat] | [nem ellenőrzött változat] |
a →Menete: link jav |
a →Álprímek: kieg |
||
17. sor: | 17. sor: | ||
Ha ''n'' összetett, és ''a^(n-1) kongruens 1 mod n'' valamely ''a'' -ra, akkor ''n a'' |
Ha ''n'' összetett, és ''a^(n-1) kongruens 1 mod n'' valamely ''a'' -ra, akkor ''n a'' |
||
alapú '''álprí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. |
||
Ha a kongruencia minden, az ''n'' -hez relatív prím ''a'' -ra fennáll, akkor ''n'' |
Ha a kongruencia minden, az ''n'' -hez relatív prím ''a'' -ra fennáll, akkor ''n'' |
||
38. sor: | 38. sor: | ||
[[Kategória:Számelmélet]] |
[[Kategória:Számelmélet]] |
||
==Források== |
==Források== |
||
*N. Koblitz: A Course in Number Theory and Cryptography 1994 |
*N. Koblitz: A Course in Number Theory and Cryptography 1994 |
A lap 2008. július 9., 21:34-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.
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 b -re is bukja a Fermat-tesztet, akkor a redukált maradékosztályoknak legalább a felére bukja.
Források
- N. Koblitz: A Course in Number Theory and Cryptography 1994
- Freud Róber - Gyarmati Edit: Számelmélet