primtalstestning

Primtalstestning är processen att avgöra om ett givet heltal är ett primtal eller inte. Ett primtal är ett naturligt tal större än 1 som inte har några positiva delare förutom 1 och sig själv. Att avgöra om ett tal är ett primtal kan vara avgörande inom kryptografi och andra områden av datorvetenskap och matematik.

Den enklaste metoden för primtalstestning är att testa alla heltal från 2 upp till kvadratroten ur det givna talet. Om något av dessa tal delar det givna talet jämnt, är det givna talet sammansatt (inte ett primtal). Om ingen av dem delar det jämnt, är det ett primtal. Denna metod kallas för "trial division" och är effektiv för mindre tal.

För större tal blir trial division opraktisk. Mer avancerade algoritmer har utvecklats, som till exempel Miller-Rabins primtalstest, som är ett probabilistiskt test. Det innebär att det kan ge ett felaktigt svar (att ett sammansatt tal identifieras som ett primtal), men sannolikheten för detta kan göras godtyckligt liten genom att köra testet flera gånger. Det finns också deterministiska algoritmer, som AKS-primtalstestet, som garanterar ett korrekt svar men är ofta mer beräkningskrävande.

Valet av primtalstest beror på talets storlek och kraven på noggrannhet. För kryptografiska tillämpningar, där mycket stora tal används, är effektiva probabilistiska tester ofta att föredra.