Wurde die Reduzierung von Shors Algorithmus ursprünglich von Shor entdeckt?

79

Dies ist mehr eine "historische Frage" als eine Forschungsfrage, aber wurde die klassische Reduktion auf die Ordnungsfindung in Shors Algorithmus zur Faktorisierung ursprünglich von Peter Shor entdeckt, oder war sie vorher bekannt? Gibt es ein Papier, das die Reduktion beschreibt, die Shor vorausgeht, oder ist es einfach ein sogenanntes "Volksergebnis"? Oder war es einfach ein weiterer Durchbruch in derselben Zeitung?

Philip White
quelle

Antworten:

139

Ich muss zugeben (überraschend, wie es sich anhört), dass ich die Antwort nicht wirklich kenne. Diese Reduktion habe ich selbst entdeckt oder wiederentdeckt.

ϕ

Obwohl ich auf die Reduzierung dieser Frage auf die Ordnungsfindung gekommen bin, ist es nicht schwer, daher wäre ich nicht überrascht, wenn es ein anderes Papier gäbe, das diese Reduzierung vor meiner beschreibt. Ich glaube jedoch nicht, dass dies ein weithin bekanntes "Volksergebnis" sein könnte. Selbst wenn es jemand entdeckt hätte, warum sollte es vor dem Quantencomputer jemand interessieren, das Factoring auf die Frage der Ordnungsfindung zu reduzieren (nachweislich exponentiell auf einem klassischen Computer)?

NN

Peter Shor
quelle
92
Hmm, ich bin nicht sicher, ob dies maßgeblich genug ist
chbaker0
5
@mebob: Macht für einen guten Skeptiker. SE post = P
Mehrdad
26
Also ... ist Shor nicht sicher?
OrangeDog
1
Tatsächlich enthält Ihr ursprüngliches PDF- Dokument aus dem Jahr 1994 den Satz „Es gibt eine zufällige Reduktion vom Faktorisieren auf die Reihenfolge eines Elements [23]“, wobei [23] wiederum auf Miller 1976 pdf verweist . Ein kurzer Blick auf diese Arbeit erlaubte mir jedoch nicht, die entsprechende Reduktion zu finden, sondern die Reduktion auf φ.
Frédéric Grosshans
2
@ Frédéric Grosshans: Eigentlich halte ich es für sehr wahrscheinlich, dass Andrew Odlyzko mich darauf hingewiesen hat.
Peter Shor
55

Die zufällige Reduktion von der Faktorisierung zur Ordnungsfindung (mod N) war in den späten 1970er und frühen 1980er Jahren sehr gut bekannt. In der Tat erscheint es in einem Aufsatz von Heather Woll, Reduktion zahlentheoretischer Probleme, Information and Computation 72 (1987) 167-179 , und Eric Bach und ich wussten es vorher.

φ(N)

Jeffrey Shallit
quelle
14
k,nfk(n)
14
Ich vermutete, Sie hatten ein viel eingeschränkteres Rechenmodell im Sinn. Aber - wie Sie sicher wissen - ist das besondere Problem, Mod N zu finden, ganz anders. Es ist also durchaus plausibel, dass die Leute über die Reduzierung dieses spezifischen Problems auf und von Factoring nachgedacht hätten.
Jeffrey Shallit
Heather Woll zitiert [1] als Quelle für die Reduktion von der Faktorisierung zur Ordnungsfindung, aber weder die Ingenieurbibliothek von Princeton noch das Departement Princeton Computer Science verfügen über eine Kopie. (Ich würde gerne eine finden, übrigens) [1] LANG. D. (1981) "Zufällige Äquivalenz von Faktorisierung und Berechnung von Ordnungen", Technical Report 284, Princeton University, Department of Electrical Engineering and Computer Science, April.
Frédéric Grosshans
2
Ich habe eine Kopie und kann sie Ihnen senden, wenn Sie mir Ihre E-Mail-Adresse senden.
Jeffrey Shallit