Hur att kontrollera om ett nummer är utmärkt

Trial division

1. 1
   Trial division är det enklaste testet för primality. Den bygger på definitionen av ett primtal. Ett antal är utmärkt om den inte har några divisors andra än sig själv och ett.
2. 2
   Låt n vara antalet du vill testa.
3. 3
   Dividera n med 2. Om resultatet är ett heltal, då är n inte främsta eftersom 2 är en faktor av n. Titta på den sista siffran och om det är ett jämnt antal, det är delbart med två. Om inte, fortsätt.
4. 4
   Dividera n med 3. Om resultatet är ett, så är n inte främsta eftersom 3 är en faktor av n. Om inte, fortsätt.
5. 5
   Fortsätt att dividera n med varje nummer mellan 2 och N ^1/2 inclusive. Om någon av dem dela jämnt, då n är inte prime eftersom du hittat en faktor. Om n har inga faktorer mindre än dess kvadratrot, då n är ett primtal. Det är tillräckligt att bara kontrollera för divisors mindre än eller lika med n ^1/2 för om n = a * b, då a och b inte kan både överstiga kvadratroten ur n.
6. 6
   Detta kan optimeras genom att hoppa över testet division med siffror som uppenbarligen inte prime. Till exempel, hoppa varje jämnt tal större än två och varje multipel av tre större än tre.

Fermats lilla sats

1. 1
   Tekniskt sett är Fermats testa ett test för compositeness, snarare än för primeness. Detta beror på att om testet misslyckas, är antalet visserligen komposit, men om testet lyckas, är antalet mycket troligt prime, men kan möjligen vara en sammansatt pseudoprime.
2. 2
   Låt n vara antalet till testet för primality.
3. 3
   Välj alla heltal a mellan 2 och n -1.
4. 4
   Beräkna a ⁿ (mod n).
   • Beräkna detta effektivt genom kvadrering istället för multiplikation när det är möjligt. Det vill säga, beräkna 3 ¹⁰⁰ som (((((((3 ²⁾ * 3) ^{2) 2) 2)} * 3) ^{2) 2,} inte som 3 * 3 * 3 * 3 *... * 3. Minska modulo n efter varje operation.
5. 5
   Kontrollera om a ⁿ = a (mod n). Om inte, är n. Om detta är sant, är n sannolikt prime. Att testet upprepas med olika värden för en kan öka förtroendet för resultatet, även om det finns sällsynta sammansatta tal som uppfyller de Fermat villkoret för alla värden på en. Dessa pseudoprimtal är Carmichael numren och den minsta är 561.

Miller-Rabin

1. 1
   Miller-Rabin testet fungerar ungefär som Fermats men hanterar patologiska fall som de carmichael siffrorna bättre.
2. 2
   Låt n vara ett udda antal för att testa för primality.
3. 3
   Faktor alla befogenheter 2 från N -1, uttrycker det i form n -1 = 2 ^s * d där d är udda.
4. 4
   Välj ett slumptal a mellan 2 och n -1.
5. 5
   Beräkna en ^d (mod n). Om en ^d = 1 eller -1 (mod n), då n passerar Miller-Rabin testet och är förmodligen prime.
6. 6
   Annars, beräkna en ^{2 d,} en ^{4 d,}... och en ^{2 s -1 d..} Om en av dessa är lika med -1 (mod n), då n är också passerar och är förmodligen prime.
7. 7
   Om n passerar Miller-Rabins test för något värde av en, prova en annan en för att öka förtroendet för resultatet av testet.
8. 8
   Om n är i själva verket, kommer den att passera med vilket värde som helst av en. Om n är sammansatt, kommer att misslyckas under minst tre fjärdedelar av värdet av en.