Hoppa till innehållet

Fermats primtalstest

Från Wikipedia

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

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 slumpmä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 gäller kongruensen trivialt. 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.

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:

Antingen ä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

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

Allmänna källor

[redigera | redigera wikitext]

Externa länkar

[redigera | redigera wikitext]