Faktorisierung < Sonstiges < Hochschule < Mathe < Vorhilfe
|
Hi,
wir bschaeftigen uns gerade mit der RSA-Encryption. Im Zuge dessen gab uns der Professor eine sehr grosse ganze Zahl:
920992759239794493492037984565126777309768092192476929111660358327361764145692724886731782219372041635323153879572347067326630382899130751718966390493
und sagte es waere sehr schwer diese zu faktorisieren. Angenommen man wollte es trotzdem schaffen, gibt es dafuer programme ?
Wie geht man da ran? Ich wuerde es wirklich gerne hinkriegen.
lg,
exeqter
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:33 Sa 14.11.2009 | | Autor: | abakus |
Hallo,
wenn sich eine Zahl z faktorisieren lässt als [mm] z=z_1*z_2 [/mm] mit [mm] z_1>z_2,
[/mm]
dann gilt [mm] z_1>\wurzel{z} [/mm] und, was wichtiger ist, [mm] z_2<\wurzel{z}.
[/mm]
Du musst also nur ein Programm schreiben, das z der Reihe nach durch die Zahlen von 2 bis [mm] \wurzel{z} [/mm] teilt.
Du verringerst die Laufzeit, wenn du
- nur ungerade Zahlen betrachtest
- du von diesen ungeraden Zahlen alle auslässt, die auf 5 enden
- du nur Primzahlen verwendest
Es dürfte allerdings schon einige Stunden (Tage/Monate?) erfordern um erst mal eine Liste der Primzahlen bis [mm] \wurzel{z} [/mm] zu erstellen.
Gruß Abakus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:54 Sa 14.11.2009 | | Autor: | MontBlanc |
hi,
ja, das habe ich mir schon gedacht, dass es schwer wird... mhh nunja, vielleicht sollte ich den gedanken begraben, scheint den aufwand nicht wert zu sein.
vielen dank trotzdem.
lg
|
|
|
|
