Laufzeitberechnung Faktorisierung

Erste Frage Aufrufe: 86     Aktiv: 01.04.2021 um 13:39

0


Mein Ansatz zur Lösung der Aufgabe ist: \(2048 * 10^{-12}\) für n einzusetzen. Als Ergebnis erhalte ich dann aber eine komplexe Zahl, und die wird wohl nicht die richtige Lösung sein.
Mir ist auch der Zusammenhang zwischen den benötigten Operationen und der 2048-Bit-Zahl nicht klar. Leider finde ich auch im dazugehörigen Kapitel des Buchs hierzu keine weiteren Hinweise. Muss man vielleicht an Stelle der 2048 die größtmögliche Zahl des Dezimalsystems verwenden, die mit 2018 Bit dargestellt werden kann?

Quelle: Beutelsbacher, Neumann, Schwarzpaul: Kryptografie in Theorie und Praxis. Wiesbaden 2010. 2. Auflage. S. 50.
Diese Frage melden
gefragt

Punkte: 10

 

Kommentar schreiben

1 Antwort
0
Mit Raten kommt man hier nicht weit. n hat in der Binärdarstellung 2048 Stellen. Nun überleg Dir, was das für den 2er-Log dieser Zahl bedeutet, und wie man von dem auf \(\ln n\) kommt.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 12.22K
 

Vielen Dank für deine Unterstützung, mikn! Allerdings hat mich dein Ansatz nicht weitergeführt.
Ich schlage hier folgende Lösung vor:
Eine Laufzeitberechnung wird immer in Abhängigkeit zur Eingabelänge vorgenommen. D.h.: Ich setze für n schlicht und einfach die Anzahl der Bits ein, also 2048.
Ergebnis: 10,29317364841327. Das Ergebnis müsste man nun noch mit \(10^{-12}\) multiplizieren, um die Lösung in Sekunden zu erhalten.
Natürlich ist dieses Ergebnis für die Faktorisierung einer Zahl mit 2048 Bit viel zu gering. Meiner Ansicht nach liegt das aber daran, dass die Formel in der Aufgabenstellung falsch ist. Ich habe mir inzwischen den Funktionsgraph dazu angeschaut. Dieser steigt nicht exponentiell, wie man es für die Faktorisierung von Zahlen erwarten dürfte. Stattdessen nähert sich der Graph einer Konstanten an. D.h.: Trotz zunehmender Anzahl von Bits bleibt die Berechnungszeit gleich. Ein solcher Faktorisierungsalgorithmus existiert mit Sicherheit nicht. Meiner Ansicht nach muss also ein Fehler in der Formel vorliegen. (Leider kann ich kein weiteres Foto anhängen, sonst hätte ich gerne noch ein Foto des Graphen gezeigt.)
  ─   bisam2000 24.03.2021 um 12:07

Nein, das geht so nicht. Es steht da ausdrücklich, dass n die zu faktorisierende Zahl ist (und nicht deren Bitlänge). Dies ist bei Faktorisierungsfragen üblich. Ich bleibe bei meinem Vorschlag.   ─   mikn 24.03.2021 um 13:33

Natürlich ist n die zu faktorisierende Zahl und nicht die Anzahl der Bits. Da gebe ich dir völlig recht. Aber es ist auch egal, welche Zahl man eingibt (größer als 2048). Das Ergebnis bleibt immer im Bereich von ca. \(10^{-11}\) Sekunden. Insofern muss die Formel auf jeden Fall falsch sein. Das Ergebnis müsste mit zunehmendem n ja grundsätzlich auf jeden Fall exponentiell ansteigen. Und das ist nicht der Fall. Der Graph nähert sich einer Konstanten an. Dein Ansatz hilft mir jedenfalls nicht weiter. Es geht ja nicht darum die Formel umzuformen. Man soll ja eine konkrete Zeitangabe ausrechnen.   ─   bisam2000 24.03.2021 um 21:19

"Natürlich..."? Du willst ja die Länge einsetzen und nicht die Zahl n selbst. Nach meiner Recherche ist in der Formel wirklich ein Fehler, der zweite Exponent sollte 2/3 sein, nicht -2/3.
In die Formel setzt man n ein, wie man auf n kommt, hab ich Dir erklärt. Damit kommt man, bei Annahme von C=1 in der O(...) Formel, auf ca. 10^19 St. Rechenzeit.
Die Laufzeit wächst subexponentiell.
  ─   mikn 24.03.2021 um 22:41

Hast du \(2^{2048}\) für n eingesetzt?   ─   bisam2000 28.03.2021 um 11:59

ja
  ─   mikn 28.03.2021 um 12:12

Wenn man \(2^{2048}\) für n einsetzt, dann setzt man also die größtmögliche mit 2048 Bit darstellbare Dezimalzahl ein. Wenn man es genau nimmt, dann ist die größtmögliche mit 2048 Bit darstellbare Dezimalzahl \(2^{2048}-1\), aber die -1 kann man wohl wegen der Größe der Zahl vernachlässigen. Im Buch steht auch auf Seite 46, dass bei Laufzeitberechnungen der "worst case" angenommen wird. Der "worst case" ist eben die größtmögliche Zahl. Man könnte ja mit 2048 Bit auch eine kleine Zahl darstellen, z.B. die Sechs. Für deren Faktorisierung würde man natürlich nicht so viel Zeit benötigen. Durch Einsetzen von \(2^{2048}\) erhält man also die Anzahl der Operationen für die Faktorisierung der Zahl und muss dann noch berücksichtigen, dass pro Sekunde \(10^{12}\) Operationen ausgeführt werden können. Deine Lösung ist bestimmt richtig! Vielen Dank für deine Hilfe!   ─   bisam2000 31.03.2021 um 12:26

Was die Größe der Zahl betrifft: Ja. Aber die Laufzeit kann man eh nicht konkret ausrechnen, weil wg O(...) nur die Größenordnung gegeben ist. Es geht also nur um die (max.) Größenordnung (auch wenn die Aufgabenstellung nach einer Laufzeit fragt). Es geht nur darum eine Idee von der Laufzeit zu kriegen.   ─   mikn 31.03.2021 um 12:32

Ok. Wenn ich also davon ausgehe, dass der letzte Exponent 2/3 lautet und nicht -2/3, dann komme ich auf das Ergebnis \(1,87021759*10^{15}\) Jahre Laufzeit.   ─   bisam2000 01.04.2021 um 12:15

Kommt hin.   ─   mikn 01.04.2021 um 13:39

Kommentar schreiben