0Pricing
Cryptology Academy · Lektion

Primzahlen und Faktorisierung

Lernen Sie, warum Primzahlen das Fundament der Public-Key-Kryptografie bilden.

Primzahlen und Faktorisierung ist eine kostenlose Cryptology Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Cryptology Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Cryptology Academy-Kurs umfasst insgesamt 4 Lektionen.

Willkommen

Primzahlen sind nur durch 1 und sich selbst teilbar. Sie sind die Atome der Multiplikation – und das Fundament von RSA, Diffie-Hellman und vielen anderen Kryptosystemen.

Definition und Beispiele

Primzahlen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... Eine Zahl ist prim, wenn ihre einzigen positiven Teiler 1 und die Zahl selbst sind. 1 ist definitionsgemäß KEINE Primzahl.

Fundamentalsatz der Arithmetik

Jede ganze Zahl > 1 lässt sich auf genau eine Weise in Primfaktoren zerlegen (bis auf deren Reihenfolge). 60 = 2² × 3 × 5. Diese Eindeutigkeit ermöglicht kryptografische Verfahren auf Basis der Faktorisierung.

Probeteilung

def is_prime(n): if n < 2: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True Es genügt, bis √n zu prüfen – wenn unterhalb von √n kein Faktor gefunden wird, ist n prim.

Sieb des Eratosthenes

Um alle Primzahlen bis N zu finden: Beginnen Sie mit einer Liste der Zahlen 2..N. Streichen Sie die Vielfachen von 2, dann von 3, dann von 5 usw. Die verbleibenden Zahlen sind prim. Der Algorithmus läuft in O(N log log N).

Primzahltest: Miller-Rabin

Für große Zahlen (2048 Bit) ist die Probeteilung zu langsam. Miller-Rabin ist ein probabilistischer Test: Wenn Sie ihn 40-mal ausführen, beträgt die Fehlerwahrscheinlichkeit < 4^(-40).

Ganzzahlfaktorisierung

Gegeben sei n = p × q. Die Bestimmung von p und q ist das Ganzzahlfaktorisierungsproblem. Wenn n 2048 Bit lang ist, benötigen die besten bekannten Algorithmen 2^112 Operationen – derzeit nicht praktikabel.

Warum RSA zwei große Primzahlen verwendet

Der RSA-Modulus ist n = p × q. Wenn n, aber nicht p und q bekannt sind, ist die Berechnung des privaten Schlüssels schwierig. Die Sicherheit beruht vollständig auf der Schwierigkeit, n zu faktorisieren.

Große Primzahlen erzeugen

from sympy import randprime p = randprime(2**1023, 2**1024) # random 1024-bit prime Oracle: Erzeugen Sie eine zufällige ungerade Zahl, testen Sie sie mit Miller-Rabin und wiederholen Sie den Vorgang, bis eine Primzahl gefunden wird.

Sichere und starke Primzahlen

Eine sichere Primzahl ist p = 2q+1, wobei q ebenfalls prim ist. Sichere Primzahlen widerstehen bestimmten Angriffen auf DH. RSA verwendet manchmal starke Primzahlen, um den Pollard-p-1-Angriff zu verhindern.

Primzahllücken und Unendlichkeit

Euklid bewies 300 v. Chr., dass es unendlich viele Primzahlen gibt. Die Vermutung über Zwillingsprimzahlen (dass es unendlich viele Primzahlen p und p+2 gibt) ist noch unbewiesen. Für die Kryptografie gehen uns niemals die Primzahlen aus.

Schnelltest

Warum verwendet RSA große Primzahlen?

Zusammenfassung

Sie verstehen nun Primzahlen und Faktorisierung. Als Nächstes wenden wir die Eulersche Phi-Funktion und den GCD an – die letzten mathematischen Werkzeuge, die wir vor RSA benötigen.

Häufig gestellte Fragen

Ist die Lektion „Primzahlen und Faktorisierung“ kostenlos?

Ja — der vollständige Text von „Primzahlen und Faktorisierung“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Cryptology Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Cryptology Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Primzahlen und Faktorisierung“?

Lernen Sie, warum Primzahlen das Fundament der Public-Key-Kryptografie bilden. Du übst Cryptology Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um Cryptology Academy zu starten?

Keine Vorkenntnisse erforderlich. Cryptology Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.

Wie lange dauert die Lektion „Primzahlen und Faktorisierung“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser Cryptology Academy-Lektion Code schreiben und ausführen?

Ja. Jede Cryptology Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

  1. Grundlagen von Binär- und Hexadezimalsystem
  2. Grundlagen der modularen Arithmetik
  3. Primzahlen und Faktorisierung
  4. GGT, Eulersche Phi-Funktion und Einführung in die Zahlentheorie
← Zurück zu Cryptology Academy