Wie kann man die Komplexität des diskreten Logarithmusproblems messen?

Die Antworten auf diese Frage in Crypto Stack Exchange besagen im Wesentlichen, dass wir zur Messung der Komplexität des Logarithmusproblems die Länge der Zahl berücksichtigen müssen, die die Größe der Gruppe darstellt. Es scheint willkürlich, warum wählen wir nicht die Größe der Gruppe als Argument? Gibt es ein Kriterium, um zu wissen, welches Argument zu wählen ist? Tatsächlich weiß ich, dass ich etwas Wichtiges übersehen habe, da sich die Komplexität enorm ändert, wenn wir dies anhand der Größe der Gruppe tun.

time-complexity discrete-mathematics cryptography Nassim HADDAM
quelle

Interessante Frage! Ich habe es so bearbeitet, dass es "die Komplexität messen" sagt, anstatt es zu "berechnen", da die Antwort darauf, wie wir es berechnen, ¯ \ _ (ツ) _ / ¯ ist. :-)

David Richerby

Ich denke es ist besser so. :)

Nassim HADDAM

Antworten:

Es spielt keine Rolle, ob Sie die Größe der Gruppe wählen oder die Größe der Ganzzahl, die als Parameter darstellt, da. Es gibt zwei Gründe, warum die Komplexität normalerweise eher mit als mit:: $|G|$ $n$ $n \approx \log |G|$ $n$ $|G|$

$n$ ist die Länge der Eingabe (genauer gesagt, die Eingabe hat die Länge ), und wir messen normalerweise die Komplexität von Algorithmen als Funktion der Eingabelänge. $\Theta(n)$
Normalerweise ist eine kleine Zahl wie , währendist eine riesige Zahl wie (ungefähr) . $n$ $1024$ $|G|$ $2^{1024}$

Yuval Filmus
quelle

Ich verstehe Ihren Standpunkt, aber macht es in P nicht zu einem Problem, wenn wir die Größe der Gruppe als Parameter wählen?

Nassim HADDAM

In diesem Fall können Sie den Parameter nicht auswählen - der Parameter ist immer die Eingabelänge.

Yuval Filmus

Danke für die Antworten. Ich hatte ein Problem damit, was passieren könnte, wenn wir den anderen Fall betrachten (Probleme in P werden in NP und umgekehrt). Ich kann jetzt klar sehen :) .

Nassim HADDAM

Wir führen die Berechnung nicht unary durch, da unser Ziel darin besteht, eine Zahl zu faktorisieren oder einen diskreten Logarithmus zu berechnen, und es ist uns egal, wie die Zahl dargestellt wird. Die Eingabe als binäre oder unäre Eingabe wirkt sich nicht auf die zur Lösung des Problems erforderliche "Wandzeit" aus, sondern nur auf die Komplexität in Bezug auf die Eingabegröße (da wir die Eingabegröße ändern!).

Yuval Filmus

Außerdem können wir nicht wirklich eine 128 Bit lange Ganzzahl als unäre Eingabe für einen realen Algorithmus haben. Es gibt nicht genug Atome im Universum.

Yuval Filmus