Är ditt tal ett primtal?

Så fungerar det

Ett primtal är ett heltal över 1 vars enda delare är 1 och talet självt: 2, 3, 5, 7, 11 och så vidare. Alla andra heltal över 1 är sammansatta och kan skrivas som en produkt av primtal på exakt ett sätt, bortsett från ordningen: 1200 = 2⁴ × 3 × 5². Talen 0 och 1 är varken primtal eller sammansatta tal.

Att dividera med alla möjliga faktorer är för långsamt för stora tal, så kontrollen använder Miller–Rabins test. Det tar en bas a och söker ett mönster i potenserna av a som alla primtal måste följa. Ett sammansatt tal bryter oftast mönstret, och basen som avslöjar det kallas ett vittne. Under ungefär 3,3 × 10²⁴ vet man att de första 13 primtalen som baser avslöjar alla sammansatta tal, så ”primtal” är där ett bevis. Över gränsen är ingen fast uppsättning bevisad. Ett tal som klarar 20 baser visas därför som ”troligen primtal”: tillräckligt säkert i praktiken, men inget bevis. ”Inte primtal” är alltid bevisat.

Primfaktorer hittas genom provdivision, vilket går direkt upp till 10¹⁵ (tusen biljoner). Över det känns ett sammansatt tal igen men faktoriseras inte här. Skillnaden är ingen slump: att testa om ett tal är ett primtal är mycket lättare än att hitta dess faktorer, och mycket av dagens kryptering bygger på det.