RSA Nummern Faktorisieren

Geht die Faktorisierung nicht viel schneller, wenn man nur eine Datenbank aller Primzahlen bis sqrt(RSA Nummer) anlegt und nur diese prüft?

Immerhin bestehen die Multiplikatoren die die RSA Nummern ergeben nur aus Primzahlen.
http://en.wikipedia.org/wiki/RSA_numbers

volkard

Primzahl schrieb:

Geht die Faktorisierung nicht viel schneller, wenn man nur eine Datenbank aller Primzahlen bis sqrt(RSA Nummer) anlegt und nur diese prüft?

Nein. Alle Primzahlen bis sqrt(RSAN) zu testen, würde bedeuten, sqrt(RSAN)/ln(sqrt(RSAN)) Teilbarkeitstests zu machen.
Da gibt es schon schnellere Verfahren, die nicht alle Primzahlen brauchen.

Außerdem überleg mal, wie groß die Datenbank sein muß. Sagen wir mal RSA1024, sqrt(2^1024)=2512
2^512/ln(2512)=sauviel. zu viel für eine datenbank.

Primzahl schrieb:

Immerhin bestehen die Multiplikatoren die die RSA Nummern ergeben nur aus Primzahlen.

Aus zwei riesigen Primzahlen.

Wenn Du deine sqrt(rsa_number)-Methode ausprobieren möchtest, dann fang am besten von hinten an. Also: ist_teilbar(rsa-numer, erste_kleinere_primzahl(sqrt(rsa_number))), dann die nächstkleinere Primzahl, usw. Eine Datenbank brauchst Du dafür nicht. Aber ich befürchte trotzdem, daß es sehr lange dauern wird.