(Twitter)
0
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
Hast du \(2^{2048}\) für n eingesetzt?
─
bisam2000
28.03.2021 um 11:59
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
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
Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden.
Mikn wurde bereits informiert.
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