Zufällige Primzahl in C generieren?
Hi,
da ich in der Schule gerade C lerne und mich selber weiterbilden möchte, wollte ich ein RSA-Verschlüsselungsprogramm programmieren. Doch ich wusste nicht, wie genau ich nun eine zufällige Primzahl generiere. Ich hatte zwar den Einfall es mit der Funktion rand zu programmieren und dann so oft eine Zahl zu generieren bis es eine Primzahl ist. Doch irgendwie kam mir das zu lang vor und wollte fragen ob das nicht ein wenig einfacher ginge?
Danke im Voraus!
3 Antworten
Soweit mir das bekannt ist werden die großen Primzahlen bei RSA so generiert, dass man zunächst eine Zufallszahl generiert, die im gewünschten Zahlenbereich ist, also eine Zahl die mal nicht zu klein ist. So kann man zB als erstes Kriterium nehmen, dass das MSB gesetzt sein muss.
Anschließend verwendet man Verfahren die sehr schnell Zahlen ausschließen können die sicher keine Primzahl ist. Da kannst du dir zB eine Tabelle mit den ersten 100 Primzahlen generieren lassen und wenn deine Zahl durch eine dieser Zahlen dividierbar ist, ist es sicher keine Primzahl.
Besteht die Zahl diesen Test muss geprüft werden ob sie tatsächlich Prim ist, zB mit einem modifizierten Sieb des Eratosthenes.
Als Anhaltspunkt kannst du mal diese Implementierung nehmen
Hier mal als Einstiegspunkt.
es gibt keine formel für eine primzahl . deswegen rechnen ja computer daran schon so lange . ergo brauchst du eine tabelle an primzahlen und wählst aus der per zufall.
oder ein anderen algo bauen der in einem bereich dann prüft und stück für stück erhöht und weiter prüft. was aber dauern kann .
Also Tabellen sind in der Kryptografie selten gut, weil du am Ende damit ja deinen Schlüsselraum massiv einschränkst, sofern die Tabelle nicht so lange ist, dass die Wahrscheinlichkeit ein und die selbe Zahl zwei mal zu wählen verschwindend gering ist.
Das Durchprobieren der Tabelle ist somit in den meisten Fällen wesentlich einfacher als das Lösen der Einwegfunktion welche die Basis des Schlüsselaustauschalgorithmus ist.
So weit mir bekannt ist, werden die Zufallszahlen bei RSA wirklich auch zufällig generiert. Also eine große Zufallszahl nehmen und dann mit einfachen schnellen Tests prüfen ob es überhaupt eine Primezahl sein kann. Anschließend mit einem genauen Test nachweisen, dass es eine Primzahl ist.