====== 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. 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?

  15%2=1
  15%3=0 ->Nein,keine Primzahl 
  
Ist 23 eine Primzahl=?

  23%2=1
  23%3=2
  23%4=3
  23%5=3
  23%6=5
  23%7=2
  23%8=7
  23%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. 

FIME Diese Seite ist in Bearbeitung.