Primtalsberegner

Primalitetstest · Faktorisering · Primtalgenerering

Indtast tal

GUIDE

Laes mere

Hvad er et primtal?

Et primtal er et naturligt tal større end 1, som ikke har andre positive divisorer end 1 og sig selv. Eksempler: 2, 3, 5, 7, 11, 13... Alle primtal undtagen 2 er ulige. Primtal er talnes "atomer".

Eratosthenes' si

En gammel algoritme udviklet af den græske matematiker Eratosthenes omkring 240 f.Kr. Den finder effektivt alle primtal op til n ved iterativt at markere multipla af hvert primtal som sammensatte.

Tvillingeprimtal

Tvillingeprimtal er par af primtal, der adskiller sig med 2: (3,5), (5,7), (11,13), (17,19)... Om der findes uendeligt mange tvillingeprimtal, er stadig et uløst problem.

Anvendelser af primtal

• RSA-kryptering: Sikkerhed baseret på vanskeligheden ved at faktorisere store tal • Hashfunktioner: Hashtabeller i primstørrelse reducerer kollisioner • Tilfældige tal: Primtal i PRNG-algoritmer • Naturen: Cikaders livscyklus bruger primtal

Definition og historie om primtal

Et primtal er et naturligt tal større end 1 uden andre divisorer end 1 og sig selv. Det mindste primtal er 2, det eneste lige primtal. Sekvens: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... Den antikke græske matematiker Euklid beviste omkring 300 f.Kr., at der findes uendeligt mange primtal. Primtal kaldes "talnes atomer", fordi hvert heltal > 1 entydigt kan opdeles i primtal (arithmetikkens fundamentalteorem). Eksempler: 60 = 2² × 3 × 5, 360 = 2³ × 3² × 5.

Algoritmer til primalitetstest

Den enkleste metode tester delelighed med alle tal fra 2 til n-1, men det er ineffektivt. En forbedring tester kun 2 til √n, da hvis n = a × b, så er a ≤ √n eller b ≤ √n. For 101: √101 ≈ 10.05, så test kun 2, 3, 5, 7. Miller-Rabin's probabilistiske test håndterer meget store tal effektivt. AKS (2002) er den første deterministiske algoritme med polynomiel tid. Moderne kryptografi bruger hundreder af cifre, hvilket kræver effektiv testning.

Eratosthenes' si-algoritme

Udviklet af den græske matematiker Eratosthenes omkring 240 f.Kr. Proces: ① Skriv tallene 2 til n. ② Markér 2 som primtal, eliminér multipla (4,6,8,10...). ③ Det næste umarkerede tal 3 er et primtal, eliminér multipla. ④ Fortsæt med 5, 7 osv. op til √n. ⑤ De resterende tal er primtal. For n=30 er primtallene 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Tidskompleksitet: O(n log log n). Kan finde alle primtal under 1 million på få sekunder.

Principper for primtalsfaktorisering

Primtalsfaktorisering udtrykker et tal som et produkt af primtal. Ifølge arithmetikkens fundamentalteorem har hvert heltal > 1 en entydig faktorisering. Metode: ① Start med det mindste primtal 2. ② Divider gentagne gange med 2, indtil tallet ikke længere er deleligt. ③ Prøv de næste primtal 3, 5, 7... ④ Fortsæt, indtil kvotienten er 1. Eksempel 360: 360÷2=180, 180÷2=90, 90÷2=45, 45÷3=15, 15÷3=5, 5÷5=1. Resultat: 360 = 2³×3²×5. Anvendelser: beregning af GCD/LCM, brøkreduktion, RSA-sikkerhed.

Tvillingeprimtal og Goldbachs formodning

Tvillingeprimtal adskiller sig med 2: (3,5), (5,7), (11,13), (17,19), (29,31)... Tvillingeprimtalsformodningen siger, at der findes uendeligt mange, men den er endnu ikke bevist. I 2013 beviste Yitang Zhang, at der findes uendeligt mange primtalpar med afstand på højst 70 millioner, senere reduceret til 246. Goldbachs formodning (1742): hvert lige tal > 2 er summen af to primtal. Eksempler: 4=2+2, 6=3+3, 8=3+5, 10=5+5. Verificeret op til 4×10¹⁸, men stadig ikke bevist.

RSA-kryptering og praktiske anvendelser

RSA-kryptering, som er kernen i internetsikkerhed, bygger på, at multiplikation er let, men faktorisering af store primtal er vanskelig. Nøglegenerering: ① Vælg store primtal p, q (1024+ bits hver). ② Beregn n = p×q (offentlig). ③ Beregn φ(n) = (p-1)(q-1). ④ Vælg offentlig eksponent e, der er primisk med φ(n) (typisk 65537). ⑤ Beregn privat eksponent d, hvor e×d ≡ 1 (mod φ(n)). Offentlig nøgle: (n,e), privat nøgle: (n,d). Krypter: C = M^e mod n, Dekrypter: M = C^d mod n. Hvis man fandt p og q ved at faktorisere n, ville krypteringen bryde sammen, men faktorisering af hundredvis af cifre tager millioner af år. Andre anvendelser: primstørrelse på hashtabeller reducerer kollisioner, cikaders 13/17-årige cyklusser undgår overlap med rovdyr, primrytmer i musik.

Ofte stillede sporgsmal

Hvilket interval kan jeg teste?

Dette værktøj understøtter primalitetstest og faktorisering for tal fra 1 til 10,000,000, mens primtalgenerering og søgning efter tvillingeprimtal virker i intervallet 2–100,000.

Hvorfor bruges primtal i kryptografi?

Det er let at gange to store primtal, men meget svært at faktorisere produktet tilbage til netop de primtal. RSA-kryptering udnytter præcis denne asymmetri til at beskytte internetkommunikation.