01
Vad är ett primtal?
Ett primtal är ett naturligt tal större än 1 som inte har några positiva delare förutom 1 och sig självt. Exempel: 2, 3, 5, 7, 11, 13... Alla primtal utom 2 är udda. Primtal är talens "atomer".
Primtalsräknare
Primtalsprov · Faktorisering · Primtalsgenerering
Las mer
02
Eratosthenes såll
En antik algoritm utvecklad av den grekiske matematikern Eratosthenes omkring 240 f.Kr. Den hittar effektivt alla primtal upp till n genom att stegvis markera multiplar av varje primtal som sammansatta.
03
Tvillingprimtal
Tvillingprimtal är primtalspare som skiljer sig åt med 2: (3,5), (5,7), (11,13), (17,19)... Om det finns oändligt många tvillingprimtal är fortfarande ett olöst problem.
04
Användningsområden för primtal
• RSA-kryptering: Säkerhet bygger på att det är svårt att faktorisera stora tal • Hashfunktioner: Hash-tabeller med primtalsstorlek minskar kollisioner • Slumptalsgenerering: Primtal i PRNG-algoritmer • Naturen: Cicadors livscykler använder primtal
05
Definition och historia för primtal
Ett primtal är ett naturligt tal större än 1 med inga delare utom 1 och sig självt. Det minsta primtalet är 2, det enda jämna primtalet. Serie: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... Den antike grekiske matematikern Euklides bevisade omkring 300 f.Kr. att det finns oändligt många primtal. Primtal kallas "talens atomer" eftersom varje heltal > 1 entydigt kan faktoriseras i primtal (aritmetikens fundamentalsats). Exempel: 60 = 2² × 3 × 5, 360 = 2³ × 3² × 5.
06
Algoritmer för primtalsprov
Den enklaste metoden testar delbarhet med alla tal från 2 till n-1, men det är ineffektivt. En förbättring testar bara 2 till √n, eftersom om n = a × b så gäller att a ≤ √n eller b ≤ √n. För 101: √101 ≈ 10.05, så testa bara 2, 3, 5, 7. Den sannolikhetsbaserade Miller-Rabin-testet hanterar mycket stora tal effektivt. AKS (2002) är den första deterministiska algoritmen med polynomisk tidskomplexitet. Modern kryptografi använder hundratals siffror, vilket kräver effektiva tester.
07
Eratosthenes såll - algoritm
Utvecklad av den grekiske matematikern Eratosthenes omkring 240 f.Kr. Process: ① Lista talen 2 till n. ② Markera 2 som primtal, stryk multiplar (4,6,8,10...). ③ Nästa omarkerade tal 3 är ett primtal, stryk multiplar. ④ Fortsätt med 5, 7, osv. upp till √n. ⑤ Återstående tal är primtal. För n=30 är primtalen 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Tidskomplexitet: O(n log log n). Kan hitta alla primtal under 1 miljon på några sekunder.
08
Principer för primtalsfaktorisering
Primtalsfaktorisering uttrycker ett tal som en produkt av primtal. Enligt aritmetikens fundamentalsats har varje heltal > 1 en unik faktorisering. Metod: ① Börja med det minsta primtalet 2. ② Dividera upprepade gånger med 2 tills det inte längre går. ③ Testa nästa primtal 3, 5, 7... ④ Fortsätt tills kvoten är 1. Exempel 360: 360÷2=180, 180÷2=90, 90÷2=45, 45÷3=15, 15÷3=5, 5÷5=1. Resultat: 360 = 2³×3²×5. Användningsområden: beräkning av GCD/LCM, förenkling av bråk, RSA-säkerhet.
09
Tvillingprimtal och Goldbachs förmodan
Tvillingprimtal skiljer sig åt med 2: (3,5), (5,7), (11,13), (17,19), (29,31)... Twin Prime Conjecture säger att oändligt många finns, men den är fortfarande obevisad. År 2013 bevisade Yitang Zhang att oändligt många primtalspare skiljer sig åt med högst 70 miljoner, senare reducerat till 246. Goldbachs förmodan (1742): varje jämnt tal > 2 är summan av två primtal. Exempel: 4=2+2, 6=3+3, 8=3+5, 10=5+5. Verifierad upp till 4×10¹⁸ men fortfarande obevisad.
10
RSA-kryptering och praktiska användningsområden
RSA-kryptering, kärnan i internetsäkerhet, bygger på att multiplikation är enkel men faktorisering av stora primtal är svår. Nyckelgenerering: ① Välj stora primtal p, q (1024+ bitar vardera). ② Beräkna n = p×q (publikt). ③ Beräkna φ(n) = (p-1)(q-1). ④ Välj offentlig exponent e som är relativt prim till φ(n) (vanligen 65537). ⑤ Beräkna privat exponent d där e×d ≡ 1 (mod φ(n)). Offentlig nyckel: (n,e), privat nyckel: (n,d). Kryptera: C = M^e mod n, Dekryptera: M = C^d mod n. Om man faktoriserar n för att hitta p,q bryts krypteringen, men faktorisering av hundratals siffror tar miljontals år. Andra användningsområden: primtalsstorlek på hash-tabeller minskar kollisioner, cikadors 13/17-årscykler undviker överlapp med rovdjur, primtalsrytmer i musik.
Vanliga fragor
Vilket intervall kan jag testa?
Det här verktyget stöder primtalsprov och faktorisering för tal från 1 till 10,000,000, medan primtalsgenerering och hitta tvillingprimtal fungerar i intervallet 2–100,000.
Varför används primtal i kryptografi?
Att multiplicera två stora primtal är enkelt, men att faktorisera produkten tillbaka till de primtalen är mycket svårt. RSA-kryptering utnyttjar just den asymmetrin för att skydda internetkommunikation.