Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:kryptographie:rsaverfahren:miller_rabin:start [19.01.2023 09:45] – angelegt Frank Schiebel
+++ faecher:informatik:oberstufe:kryptographie:rsaverfahren:miller_rabin:start [06.06.2024 15:39] (aktuell) – Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
 ====== Hintergrund: Große Primzahlen - das Miller Rabin Verfahren ======
-Ein praktisches Problem bei der Anwendung des [[..start|RSA Verfahrens]] ist es, die - sehr großen - Primzahlen p und q zu erhalten
+Ein praktisches Problem bei der Anwendung des [[..start|RSA Verfahrens]] ist es, die - sehr großen - Primzahlen p und q zu erhalten. RSA mit 2048 Bit Schlüssellänge verwendet momentan etwa 300-stellige Primzahlen, die man bei der Erzeugung des Schlüsselpaars zunächst möglichst zufällig "finden" muss.
+Da es keine Möglichkeit gibt Primzahlen zu "berechnen", bleibt nur der Weg, eine Zufallszahl z zu erzeugen und anschließend zu überprüfen, ob diese Zufallszahl eine Primzahl ist oder nicht.
+Bei einer naiven Herangehensweise muss man also prüfen, ob es eine Zahl gibt,die kleiner als die Zahl z ist und diese ohne Rest teilt.
+=== Beispiele: ===
+Ist z=15 eine Primzahl?
+%2=1
+%3=0 ->Nein,keine Primzahl
+Ist 23 eine Primzahl=?
+%2=1
+%3=2
+%4=3
+%5=3
+%6=5
+%7=2
+%8=7
+%9=5
+  ...-> Ja 23 ist eine Primzahl
+Man sieht schnell, dass dieses Verfahren auch mit Unterstützung moderner Computer bei großen Zahlen schnell an eine Grenzen stößt.
+FIXME Diese Seite ist in Bearbeitung.