Sieb des Eratosthenes

Das Sieb des Eratosthenes ist ein einfaches, effizientes Verfahren, um alle Primzahlen bis zu einer bestimmten Grenze zu finden, indem man wiederholt Vielfache von Primzahlen aus einer Liste streicht.

    Wie funktioniert der Algorithmus?

  • Der Algorithmus "Sieb des Eratosthenes" berechnet alle Primzahlen bis zu einer gegebenen Obergrenze Primzahlen sind natürliche Zahlen größer als 1, die nur durch 1 und sich selbst ohne Rest teilbar sind.
  • Schreiben Sie alle Zahlen von 2 bis zu einer gewünschten Obergrenze auf.
  • Streichen Sie alle Vielfachen von 2 außer der Zahl 2 selbst.
  • Fahren Sie mit der nächsten nicht gestrichenen Zahl fort und streichen Sie deren Vielfache.
  • Wiederholen Sie diesen Vorgang, bis keine Vielfachen mehr gestrichen werden können.
  • Die verbleibenden Zahlen sind Primzahlen.

    • Was berechnet der Algorithmus?

    Der Algorithmus Sieb des Eratosthenes berechnet alle Primzahlen bis zu einer gegebenen Obergrenze. Primzahlen sind natürliche Zahlen größer als 1, die nur durch 1 und sich selbst ohne Rest teilbar sind.

    Wie funktioniert der Algorithmus?

    Der Ablauf des Sieb des Eratosthenes ist folgendermaßen aufgebaut:

    1. Schreibe alle Zahlen von 2 bis n auf.
    2. Beginne bei der kleinsten noch nicht gestrichenen Zahl (zuerst 2).
      • Diese Zahl ist eine Primzahl.
      • Streiche alle Vielfachen dieser Zahl, die größer als sie selbst sind.
    3. Gehe zur nächsten noch nicht gestrichenen Zahl.
      • Diese Zahl ist ebenfalls eine Primzahl.
      • Streiche wieder alle ihre Vielfachen (größer als sie selbst).
    4. Wiederhole diesen Vorgang, bis alle Zahlen bis zur Quadratwurzel von n (√n) überprüft wurden.

    Am Ende bleiben nur die Primzahlen übrig – alle anderen Zahlen wurden gestrichen.

    Beispiel für n = 30:

    • Beginne mit 2: streiche 4, 6, 8, 10, 12, …
    • Nächste Primzahl 3: streiche 6, 9, 12, 15, 18, …
    • Nächste Primzahl 5: streiche 10, 15, 20, 25, 30
    • usw.

    Wie kann man den Algorithmus nutzen, um zu testen, ob eine Zahl n für RSA geeignet ist?

    Für RSA, ein verbreitetes Verschlüsselungsverfahren, werden große Primzahlen benötigt. Der Sieb des Eratosthenes kann dabei unterstützen:

    • Zunächst lassen sich mit dem Sieb des Eratosthenes alle Primzahlen bis etwa √n berechnen.
    • Anschließend prüft man, ob n durch eine dieser Primzahlen teilbar ist.
      • Wenn ja: n ist zusammengesetzt → ungeeignet für RSA.
      • Wenn nein: n hat keine kleinen Teiler → möglicherweise geeignet für RSA.

    Hinweis:

    • Bei sehr großen Zahlen (z. B. mit 1024 Bit Länge), wie sie in der Praxis verwendet werden, ist der klassische Sieb zu aufwendig.
    • Deshalb setzt man in der Kryptographie effizientere Verfahren wie den Miller-Rabin-Test ein. Sie verfolgen zwar einen anderen Ansatz, beruhen aber auf demselben Grundprinzip: das Finden potenzieller Teiler.