Primtal, Eratosthenes såll och att få betalt för primtal

2013-09-24 Av Simon Rybrand 1 kommentar

I det här blogginlägget skall vi kika närmare på det som kallas för primtal. Vi skall undersöka hur man egentligen kan hitta hitta dessa tal, vad de används till och om man kan få bra betalt för att hitta dem?

Vad ett primtal är och vad de är bra för

Ett primtal är ett tal som endast är delbart med 1 och sig själv. Vad betyder egentligen detta? Jo för att ett tal p skall vara ett primtal så kan det inte finnas något tal mellan 1 och p som delar just det tal (så att ett helta ges som resultat).

Exempel på primtal kan vara 7, 23 eller 29. Inget av dessa tal kan delas med något annat än sig själv eller 1. Exempel på tal som inte är primtal kan vara 9, 15, 21. Alla dessa tal är exempelvis delbara med talet 3.

Så vad används egentligen primtal till? Idag är det framförallt inom datorsäkerhet som dessa primtal används inom det som kallas för RSA kryptering. Dessa tal och produkter av dessa har visat sig vara mycket användbara för att säkert kunna skicka information mellan datorer.

Hur hittar du primtal på ett effektivt sätt?

Matematiker har genom alla tider varit väldigt intresserade av primtal och letat efter de allra bästa algoritmerna för att hitta just primtal. I vissa fall så har även detta visat sig vara lönsamt (se mer nedan).

I den allra enklaste formen av algoritm (instruktioner/metod för att lösa något eller hitta något) så skulle man kunna ta ett tal och sedan testa om det finns något tal mindre än detta tal som delar ursprungstalet. Det här innebär att algoritmen kommer att vara väldigt ineffektiv. Om vi letar efter mycket stora primtal så kommer vi (dvs datorn) att få jobba väldigt, väldigt mycket.

Nu finns det diverse olika algoritmer för att snabbare hitta primtal där den kändaste nog är Eratosthenes såll. Eratosthenes levde cirka 200 f.Kr. och är bland annat känd för att han kunde bestämma jordens storlek. Han gjorde alltså även en algoritm kallad för Eratosthenes såll som lyder enligt följande:

1. Gör en lista på alla tal från 2 till ett högsta tal, vi kallar det högsta talet för m.
2. Ta bort alla jämna tal från listan som är större än 2. (Ett alternativ för oss som har datorer är att direkt göra en lista på alla udda tal större än 2).
3. Det första talet i listan är nu ett primtal (talet 3 vid första iterationen).
4. Ta nu bort alla tal som är delbara av det första primtalet. Dessa tal kan ju inte vara ett primtal.
5. Upprepa nu steg 3 och 4 tills du har nått ett tal som är större än kvadratroten ur ditt maxtal m.
6. De tal som blir kvar i listan är nu primtal.

Om du sätter dig in i metoden här ovan så kommer du att märka att i jämförelse med den första, mer tidskrävande metoden, så finns det ett antal olika effektiviseringar av algoritmen. Men många matematiker anser ändå att denna metod är allt för tidskrävande och effektiv och har därför utvecklat ännu mer avancerade metoder för att hitta så stora primtal som möjligt.

Bland annat så finns det ett projekt som heter GIMPS (Great Internet Mersenne Prime Search) där man använder internets hjälp för att använda flera datorer världen över för att hitta primtal. Med hjälp av detta har de hittat det enormt stora primtalet $2^{57,885,161}-1$.

Kan man få betalt för att hitta primtal?

Ibland hör man rykten om att det faktiskt skulle kunna gå att tjäna pengar på att hitta primtal då dessa är så eftertraktade inom kryptografin. Detta stämmer dock bara med viss modifikation. Det finns visserligen priser som belönar de som hittar extremt stora primtal. Du kan exempelvis få 250 000 $ av Electronic Frontier Foundation om du hittar ett primtal med över 1,000,000,000 siffror. Det här är dock extremt svårt och kräver mängder av datorkapacitet och tur.

Men att företag som använder RSA kryptering skulle vara intresserade av stora primtal stämmer tydligen inte. Det behövs egentligen inte särskilt stora primtal för att just denna typ av kryptering skall vara säker.