Fermats primtalstest
Fermats primtalstest är ett probabilistiskt test för att avgöra om ett tal är ett misstänkt primtal.
Essens
Fermats lilla sats säger att om är ett primtal och om inte är delbart med så gäller att:
Om man vill testa om är ett primtal så kan man välja ett slummässigt heltal som inte delbart med och se om likheten stämmer. Om likheten inte stämmer för ett värde av så är ett sammansatt tal. Det är osannolikt att denna kongruens kommer att hålla för slumpmässiga värden av om är ett sammansatt tal.[1] Man säger därför att är ett misstänkt primtal för ett eller flera värden på om likheten håller.
Observera dock att för så hålls kongruensen triviellt. Det gäller också trivialt om är udda och . Av just denna anledning väljer man vanligtvis ett tal i intervallet .
För alla tal så att:
när är ett sammansatt tal så är känd som en Fermatlögnare. I detta fall kallas för ett Fermatpseudoprimtal till basen . Om man istället väljer ett tal så att:
då är känd som ett Fermatvittne.
Exempel
Anta att vi vill ta reda på om 221 är ett primtal eller inte. Slumpmässigt välj ett tal i intervallet , låt oss säga 38. Vi kontrollerar ovanstående likhet och som om det håller:
Antigen så är 221 ett primtal eller så är 38 en Fermatlögnare. Vi testar igen med ett annat tal , låt oss säga 24:
Så är 221 är garanterat ett sammansatt tal och 38 var en Fermatlögnare.
Programmering
Nedan visas implementeringen av Fermats primtalstest i programmering. Koden använder en exponentialfunktion från modulär exponentiering.[2] I exemplet nedan så används C++ som programmeringsspråk:
// Om n är ett primtal retuneras det alltid som sant
// Om n är ett sammansatt tal retuneras det som falskt med hög sannolikhet
// Högre värde på k ökar sannolikheten för det blir rätt resultat
bool isPrime(unsigned int n, int k)
{
// Patologiska fall
if (n <= 1 || n == 4) return false;
if (n <= 3) return true;
// Försök k gånger
while (k>0)
{
// Välj ett slumpmässigt tal i [2..n-2]
// Se till att n > 4 är ovanför det patologiska fallet
int a = 2 + rand()%(n-4);
// Kontrollerar om a och n är relativt prima
if (gcd(n, a) != 1)
return false;
// Fermats lilla sats
if (power(a, n-1, n) != 1)
return false;
k--;
}
return true;
}
Referenser
Allmänna källor
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford S. (2001). ”Primality testing” (på engelska). Introduction to Algorithms (2). McGraw-Hill: MIT Press. sid. 889–890. Libris länk. ISBN 0-262-03293-7. OCLC 46792720.
Källor
- ^ Pomerance, Carl; Selfridge, John Lewis; Wagstaff, Samuel Standfield (juli 1980). ”The Pseudoprimes to 25·109” (på engelska). Mathematics of Computation (Washington: American Mathematical Society) 35 (151): sid. 1003–1003. doi: . JSTOR 2006210. ISSN 0025-5718. OCLC 1173748874. https://www.ams.org/journals/mcom/1980-35-151/S0025-5718-1980-0572872-7/S0025-5718-1980-0572872-7.pdf. Läst 23 juli 2020.
- ^ ”Primality Test | Set 2 (Fermat Method)” (på engelska). GeeksforGeeks. Arkiverad från originalet den 23 juli 2020. https://archive.vn/PS9wd#selection-13545.49-13551.5. Läst 23 juli 2020.
Externa länkar
- Enkel videoförklaring av Fermats primtalstest på YouTube av Numberphile (engelska)
- Enkel förklaring av Fermats primtalstest på The Math Less Traveled av Brent Yorgey (engelska)