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.

    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.
  • 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.

    • Schrift 1

    Was berechnet der Algorithmus?

    Der Algorithmus Sieb des Eratosthenes berechnet alle Primzahlen bis zu einer gegebenen Obergrenze \( n \). 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:

    1. Schreibe alle Zahlen von 2 bis n auf.
    2. Beginne bei der kleinsten Zahl (zuerst 2).
      • Diese Zahl ist eine Primzahl.
      • Streiche alle Vielfachen dieser Zahl (außer die Zahl selbst).
    3. Gehe zur nächsten noch nicht gestrichenen Zahl und wiederhole den Vorgang:
      • Sie ist wieder eine Primzahl.
      • Streiche ihre Vielfachen.
    4. Wiederhole dies, bis alle Zahlen bis sqrt{n} überprüft sind.

    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 Verschlüsselungsverfahren) braucht man große Primzahlen. Der Sieb des Eratosthenes hilft so:

    • Um zu prüfen, ob eine Zahl n eine Primzahl ist, könnte man alle Primzahlen bis etwa sqrt{n} mit dem Sieb des Eratosthenes berechnen.
    • Dann testet man, ob n durch eine dieser Primzahlen teilbar ist.
      • Falls ja: n ist keine Primzahl → ungeeignet für RSA.
      • Falls nein: n ist wahrscheinlich eine Primzahl → möglicherweise geeignet für RSA.

    Hinweis:

    • Für große Zahlen (z.B. 1024 Bit lang) wie bei echtem RSA ist der klassische Sieb zu langsam und speicherintensiv.
    • Praktisch nutzt man deshalb schnellere Primzahltests (z.B. Miller-Rabin-Test), aber die Idee bleibt ähnlich: prüfen, ob es kleine Teiler gibt.