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

9

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.

Nassim HADDAM
quelle
2
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:

5

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|nnlog|G|n|G|

  1. 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.Θ(n)

  2. Normalerweise ist eine kleine Zahl wie , währendist eine riesige Zahl wie (ungefähr) .n1024|G|21024

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
1
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
1
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
1
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