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 ${\textstyle p}$ är ett primtal och om ${\textstyle a}$ inte är delbart med ${\textstyle p}$ så gäller att:

$a^{p-1}\equiv 1{\pmod {p}}$

Om man vill testa om ${\textstyle p}$ är ett primtal så kan man välja ett slummässigt heltal ${\textstyle a}$ som inte delbart med ${\textstyle p}$ och se om likheten stämmer. Om likheten inte stämmer för ett värde av ${\textstyle a}$ så är ${\textstyle p}$ ett sammansatt tal. Det är osannolikt att denna kongruens kommer att hålla för slumpmässiga värden av ${\textstyle a}$ om ${\textstyle p}$ är ett sammansatt tal. Man säger därför att ${\textstyle p}$ är ett misstänkt primtal för ett eller flera värden på ${\textstyle a}$ om likheten håller.

Observera dock att för ${\textstyle a^{p-1}\equiv 1{\pmod {p}}}$ så hålls kongruensen triviellt. Det gäller också trivialt om ${\textstyle p}$ är udda och ${\textstyle a\equiv -1{\pmod {p}}}$. Av just denna anledning väljer man vanligtvis ett tal ${\textstyle a}$ i intervallet ${\textstyle 1<a<p-1}$.

För alla tal ${\textstyle a}$ så att:

$a^{n-1}\equiv 1{\pmod {n}}$

när ${\textstyle n}$ är ett sammansatt tal så är ${\textstyle a}$ känd som en Fermatlögnare. I detta fall kallas ${\textstyle n}$ för ett Fermatpseudoprimtal till basen ${\textstyle a}$. Om man istället väljer ett tal ${\textstyle a}$ så att:

$a^{n-1}\not \equiv 1{\pmod {n}}$

då är ${\textstyle a}$ 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 ${\textstyle a}$ i intervallet ${\textstyle 1<a<220}$, låt oss säga 38. Vi kontrollerar ovanstående likhet och som om det håller:

$a^{n-1}=38^{220}\equiv 1{\pmod {221}}$

Antigen så är 221 ett primtal eller så är 38 en Fermatlögnare. Vi testar igen med ett annat tal ${\textstyle a}$, låt oss säga 24:

$a^{n-1}=24^{220}\equiv 81\not \equiv 1{\pmod {221}}$

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. 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.

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)