Util Monster
Kostenlos
Primzahltest · Zerlegung · Primzahlgenerierung
Eine Primzahl ist eine natürliche Zahl größer als 1, die außer 1 und sich selbst keine positiven Teiler hat. Beispiele: 2, 3, 5, 7, 11, 13... Alle Primzahlen außer 2 sind ungerade. Primzahlen sind die "Atome der Zahlen."
Ein antiker Algorithmus des griechischen Mathematikers Eratosthenes aus etwa 240 v. Chr. Er findet effizient alle Primzahlen bis n, indem er die Vielfachen jeder Primzahl schrittweise als zusammengesetzt markiert.
Primzahlpaare sind Primzahlen mit einem Abstand von 2: (3,5), (5,7), (11,13), (17,19)... Ob es unendlich viele Primzahlpaare gibt, ist bis heute ungeklärt.
• RSA-Verschlüsselung: Sicherheit basiert auf der Schwierigkeit, große Zahlen zu faktorisieren • Hash-Funktionen: Hash-Tabellen mit Primzahlgröße reduzieren Kollisionen • Zufallszahlengenerierung: Primzahlen in PRNG-Algorithmen • Natur: Lebenszyklen von Zikaden nutzen Primzahlen
Eine Primzahl ist eine natürliche Zahl größer als 1 ohne Teiler außer 1 und sich selbst. Die kleinste Primzahl ist 2, die einzige gerade Primzahl. Folge: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... Der antike griechische Mathematiker Euklid bewies um 300 v. Chr., dass es unendlich viele Primzahlen gibt. Primzahlen werden die "Atome der Zahlen" genannt, weil sich jede ganze Zahl > 1 eindeutig in Primzahlen zerlegen lässt (Fundamentalsatz der Arithmetik). Beispiele: 60 = 2² × 3 × 5, 360 = 2³ × 3² × 5.
Die einfachste Methode prüft die Teilbarkeit durch alle Zahlen von 2 bis n-1, ist aber ineffizient. Eine Verbesserung prüft nur 2 bis √n, denn wenn n = a × b, dann gilt a ≤ √n oder b ≤ √n. Für 101: √101 ≈ 10,05, also werden nur 2, 3, 5, 7 geprüft. Der probabilistische Miller-Rabin-Test eignet sich effizient für sehr große Zahlen. AKS (2002) ist der erste deterministische Algorithmus in Polynomialzeit. Moderne Kryptografie arbeitet mit hunderten Stellen und benötigt daher effiziente Tests.
Entwickelt vom griechischen Mathematiker Eratosthenes um 240 v. Chr. Ablauf: ① Zahlen von 2 bis n auflisten. ② 2 als prim markieren, Vielfache streichen (4,6,8,10...). ③ Die nächste unmarkierte Zahl 3 ist prim, ihre Vielfachen streichen. ④ Mit 5, 7 usw. bis √n fortfahren. ⑤ Die verbleibenden Zahlen sind prim. Für n=30 sind die Primzahlen 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Zeitkomplexität: O(n log log n). Kann alle Primzahlen unter 1 Million in Sekunden finden.
Die Primfaktorzerlegung stellt eine Zahl als Produkt von Primzahlen dar. Nach dem Fundamentalsatz hat jede ganze Zahl > 1 eine eindeutige Zerlegung. Vorgehen: ① Mit der kleinsten Primzahl 2 beginnen. ② Wiederholt durch 2 teilen, bis keine Teilbarkeit mehr besteht. ③ Die nächsten Primzahlen 3, 5, 7... testen. ④ Fortfahren, bis der Quotient 1 ist. Beispiel 360: 360÷2=180, 180÷2=90, 90÷2=45, 45÷3=15, 15÷3=5, 5÷5=1. Ergebnis: 360 = 2³×3²×5. Anwendungen: Berechnung von ggT/kgV, Bruchkürzung, RSA-Sicherheit.
Primzahlpaare unterscheiden sich um 2: (3,5), (5,7), (11,13), (17,19), (29,31)... Die Primzahlpaarvermutung besagt, dass es unendlich viele davon gibt, ist aber bis heute nicht bewiesen. 2013 bewies Yitang Zhang, dass unendlich viele Primzahlpaare einen Abstand von höchstens 70 Millionen haben; später wurde die Schranke auf 246 reduziert. Goldbachsche Vermutung (1742): Jede gerade Zahl > 2 ist die Summe zweier Primzahlen. Beispiele: 4=2+2, 6=3+3, 8=3+5, 10=5+5. Bis 4×10¹⁸ überprüft, aber weiterhin unbewiesen.
RSA-Verschlüsselung, das Kernstück der Internetsicherheit, beruht darauf, dass das Multiplizieren leicht, das Faktorisieren großer Primzahlen aber schwer ist. Schlüsselerzeugung: ① Große Primzahlen p, q wählen (je 1024+ Bit). ② n = p×q berechnen (öffentlich). ③ φ(n) = (p-1)(q-1) berechnen. ④ Öffentlichen Exponenten e wählen, der zu φ(n) teilerfremd ist (meist 65537). ⑤ Privaten Exponenten d berechnen, sodass e×d ≡ 1 (mod φ(n)). Öffentlicher Schlüssel: (n,e), privater Schlüssel: (n,d). Verschlüsselung: C = M^e mod n, Entschlüsselung: M = C^d mod n. Das Faktorisieren von n zur Bestimmung von p,q würde die Verschlüsselung brechen, aber das Faktorisieren von Zahlen mit hunderten Stellen dauert Millionen von Jahren. Weitere Anwendungen: Primzahlgrößen für Hash-Tabellen verringern Kollisionen, 13/17-jährige Zikadenzyklen vermeiden Überschneidungen mit Fressfeinden, Primrhythmen in der Musik.