RSA Verfahren, p und q abschätzen um N mit einem brute-force Ansatz zu faktorisieren.

Question

Hi,

Frage:

"Es seinen N = 1 032 247 und e = 686 811 die öffentlichen Daten für das RSA-Verfahren. Schätzen Sie ab, wieviele mögliche Zahlen p und q Sie untersuchen müssen, um N mit einem brute-force Ansatz zu faktorisieren."


die Frage bei der ich nicht weiter komme, steht oben im Titel. Zwar weiß ich wie man diese große Zahl faktorisiert (es gibt ja einige Methoden dafür) aber ich habe leider keine Ahnung wie man das via Brute-Force abschätzt... Brute Force wäre ja 2*3, 2*5, 2*7,...,3*5, 3*7,..., 5*7,...,p*q solange halt bis man halt p und q findet aber wie zum Teufel kann man das abschätzen :(

Vielen Dank für Tipps und Tricks :)

Answer 1

Die Frage ist in der Tat sehr schwammig gestellt. Um einen Prinfaktor von N zu finden, genügt es die Primzahlen bis \( \sqrt{N} \) zu betrachten. Es ist $$\pi (\sqrt{N})=\pi (1015)=170$$, mit pi die Primzahlfunktion.

Comments

Ok, dass hört sich doch schonmal gut an :) aber kannst du mir erklären, wie man von π(1015) auf 170 kommt hab noch nie was von dieser Pi-Funktion gehört. (Wenn ich 1015/ln(1015) (Hab ich jetzt iwo aussem Internet auf die Schnelle gegoogelt) rechne, bin ich bei 147)

---

Den Wert hat mir mein CAS berechnet. Was auch immer du gegoogelt hast, du hast offensichtlich nur halb gelesen. Es ist $$ \lim_{x\to \infty} \frac{\pi (x)} {\frac{x}{log(x)}} =1 $$, ohne den Limes gilt das nicht.