Fermats primtalstest

Fermats primtalstest är ett probabilistiskt test för att avgöra om ett tal är ett misstänkt primtal.

Essens[redigera | redigera wikitext]

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 slumpmä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.^[1] 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}}}$ gäller kongruensen trivialt. 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[redigera | redigera wikitext]

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

Antingen ä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[redigera | redigera wikitext]

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:

bool isPrime(unsigned int n, int k) 
{ 
   if (n <= 1 || n == 4)  return false; 
   if (n <= 3) return true;

   while (k>0) 
   {

       int a = 2 + rand()%(n-4);   
  
       if (gcd(n, a) != 1) 
          return false; 
   
       if (power(a, n-1, n) != 1) 
          return false; 
  
       k--; 
    } 
  
    return true; 
}