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

$a^{p-1}\equiv 1(\mathrm{mod}p)$

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

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

För alla tal $a$ så att:

$a^{n-1}\equiv 1(\mathrm{mod}n)$

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

$a^{n-1}\equiv ̸1(\mathrm{mod}n)$

då är $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 $a$ i intervallet $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(\mathrm{mod}221)$

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

$a^{n-1}=24^{220}\equiv 81\equiv ̸1(\mathrm{mod}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:

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

Referenser

Allmänna källor

• Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (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. Läst 23 juli 2020.

Externa länkar

• Enkel videoförklaring av Fermats primtalstest på YouTube av Numberphile Mall:Språkikon
• Enkel förklaring av Fermats primtalstest på The Math Less Traveled av Brent Yorgey Mall:Språkikon