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

a
hiv. korr, AWB
a (→‎Menete: euklidészi→euklideszi with AWB)
a (hiv. korr, AWB)
A '''Fermat-prímteszt''' (vagy Fermat-féle prímszámpróba) egy valószínűségi prímteszt. A [[kis Fermat-tétel]]en alapul, ami kimondja, hogy ha ''p'' [[PrímszámPrímszámok|prím]], akkor
''a''<sup>''p''-1</sup> [[kongruencia|kongruens]] ''1'' mod ''p'', ha ''p'' nem osztója ''a''-nak.
 
Legyen most ''n'' páratlan pozitív egész. Teljesül a következő
 
'''Tétel:'''
 
1. ''n'' [[bikondicionális|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<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
 
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''^(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''<sub>1</sub>)<sup>''d''</sup>(''b''<sub>2</sub>)<sup>''d''</sup>=(''b''<sub>1</sub>''b''<sub>2</sub>)<sup>''d''</sup> (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''<sub>1</sub><''b''<sub>2</sub>< … <''b''<sub>''k''</sub> 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''<sub>1</sub><''b''<sub>2</sub>< … <''b''<sub>''k''</sub> számokat, ezek páronként inkongruensek lesznek.
 
'''Állítás''' - ''n'' bukja a tesztet ezekre a ''tb''<sub>1</sub><''tb''<sub>2</sub>< … <''tb''<sub>''k''</sub> számokra.
 
==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:
2. Minden ''p'' prímosztójára ''p-1'' osztója ''n-1'' -nek.
 
'''Bizonyítás'''
 
1. Tegyük fel, hogy ''p''<sup>2</sup> osztója ''n'' -nek. Belátjuk, hogy ''n'' nem lehet Carmichael-szám.
''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.
ahol ''m=n/p'', és ''g'' primitív gyök ''mod 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''<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''
297 612

szerkesztés