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 ä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.
Exempel
[redigera | redigera wikitext]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;
}
Referenser
[redigera | redigera wikitext]Allmänna källor
[redigera | redigera wikitext]- 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.
Källor
[redigera | redigera wikitext]- ^ 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.today/20200723085023/https://www.geeksforgeeks.org/primality-test-set-2-fermet-method/. Läst 23 juli 2020.
Externa länkar
[redigera | redigera wikitext]- 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)