Der diskrete Logarithmus ist derselbe wie in , wenn , und .
Ich frage mich, in welchen Komplexitätsgruppen (z. B. für klassische Computer und Quantencomputer) sich dies befindet und welche Ansätze (dh Algorithmen) sich am besten für diese Aufgabe eignen.
Der obige Wikipedia-Link gibt nicht wirklich konkrete Laufzeiten an. Ich hoffe auf etwas Ähnliches wie die bekanntesten Methoden, um solche zu finden.
Antworten:
Kurze Antwort.
Wenn wir eine geeignete Entscheidungsproblemversion des Diskreten Logarithmus-Problems formulieren , können wir zeigen, dass es zum Schnittpunkt der Komplexitätsklassen NP , coNP und BQP gehört .
Eine Entscheidungsproblemversion von Discrete Log.
Das diskrete Logarithmusproblem wird meist als Funktionsproblem formuliert , bei dem Tupel von ganzen Zahlen einer anderen ganzen Zahl zugeordnet werden. Diese Formulierung des Problems ist nicht kompatibel mit den Komplexitätsklassen P , BPP , NP usw., die von den Menschen bevorzugt berücksichtigt werden und nur Entscheidungsprobleme (Ja / Nein) betreffen . Wir können eine Entscheidungsproblemversion des diskreten Protokollproblems in Betracht ziehen, die effektiv äquivalent ist:
Dies würde es uns ermöglichen, log a ( c ) modulo N durch binäre Suche tatsächlich zu berechnen , wenn wir es effizient lösen könnten. Wir können dann fragen, zu welchen Komplexitätsklassen dieses Problem gehört. Beachten Sie, dass wir es als ein Versprechensproblem formuliert haben: Wir können es auf ein Entscheidungsproblem , indem wir die Anforderungen aussetzen, dass Primzahl und Generator ist, aber die Bedingung hinzufügen, für die diese Einschränkungen gelten JEDE JA-Instanz des Problems.N a∈Z×N
Diskretes Protokoll ist in BQP.
Unter Verwendung des Shor-Algorithmus zur Berechnung des diskreten Logarithmus ( Polynomial-Time-Algorithmus zur Primfaktorisierung und diskreten Logarithmen auf einem Quantencomputer ) kann Discrete Log in BQP leicht enthalten sein . (Um zu testen, ob tatsächlich ein Generator ist, können wir Shors Algorithmus zur Ordnungsfindung in derselben Veröffentlichung verwenden, der die Grundlage für den diskreten Logarithmus ist, um die Ordnung von und zu ermitteln Vergleiche es mit .)
Diskretes Protokoll ist in NP NP coNP.
Wenn es tatsächlich so ist, dass eine Primzahl ist und ein Generator ist, ist ein ausreichendes Zertifikat entweder für eine 'YES'- oder eine' NO'-Instanz des Entscheidungsproblems die eindeutige Ganzzahl so dass . Es reicht also zu zeigen, dass wir zertifizieren können, ob die Bedingungen für und gelten oder nicht . Nach Brassards Ein Hinweis auf die Komplexität der Kryptographie , wenn es sowohl der Fall , dass eine Primzahl ist und ein Generator ist, dann ist es der Fall , dass
Ein Zertifikat , das die Beschränkungen für und beide halten würde eine Liste der Primfaktoren sein Dividieren , die uns die obigen Einschränkungen Kongruenz testen können. (Wir können testen, ob jedes eine Primzahl ist, indem wir AKS-Test verwenden , und testen, ob dies alle Primfaktoren von indem wir versuchen, die Primzahlfaktorisierung von nur mit diesen Primzahlen zu finden.)N a q1,q2,… N−1 qj N−1 N−1
Ein Zertifikat, dass eine der Bedingungen für oder Fehler eine ganze Zahl die teilt , so dass . In diesem Fall ist es nicht erforderlich, auf Primität zu prüfen . es impliziert sofort, dass die Ordnung von kleiner als , und ist daher nur dann ein Generator der multiplikativen Gruppe, wenn keine Primzahl ist.N a q N−1 a(N−1)/q≡1(modN) q a N−1 N
quelle
Im allgemeinen und im schlimmsten Fall ist die Antwort von Niel de Beaudrap nach meinem besten Wissen richtig.
Für den Fall, dass nur kleine Primfaktoren hat, findet der Pohlig-Hellman-Algorithmus den Logarithmus in Zeit. Daher ist für diesen Fall ist die Discrete Log Problem in . Wenn ein kryptografisches Protokoll von der Härte dieses Problems abhängt, ist es daher wichtig, den Modul so zu wählen , dass große Primfaktoren aufweist.N−1 O(log2(N)) P N N−1
quelle
da , dann ist . (Bedeutet, Brute-Force ist in EXP.)|a|=O(N) b=O(N)
Für eine nicht deterministische Maschine gibt es ein polynomisches Zeugnis, da wir in P. eine modulare Exponentiation durchführen können (dh das Problem liegt in .)NP
Die Theorie, dass diskrete Logarithmen in und nicht in ist die Grundlage der modernen Kryptographie, aber das ist offensichtlich nicht bewiesen.NP P
Shors Methode (auf dieser Wikipedia-Seite verlinkt) läuft in polynomialer Zeit auf einem Quantencomputer.
quelle