Warum wird die modulare Exponentiation nach Montgomery nicht für die Verwendung im Quantenfaktor berücksichtigt?

20

Es ist bekannt, dass die modulare Exponentiation (der Hauptteil einer RSA-Operation) rechenintensiv ist, und meines Wissens ist die Technik der modularen Exponentiation nach Montgomery die bevorzugte Methode. Modulare Exponentiation spielt auch im Quantenfaktor-Algorithmus eine wichtige Rolle und ist dort auch teuer.

Also: Warum ist die modulare Exponentiation von Montgomery in aktuellen detaillierten Subroutinen für das Quantum Factoring offenbar nicht vorhanden?

Das Einzige, was ich mir vorstellen kann, ist, dass es aus irgendeinem nicht offensichtlichen Grund einen hohen Qubit-Overhead gibt.

Das Ausführen der "modularen Exponentiation" von Montgomery Quantum durch Google Scholar liefert keine nützlichen Ergebnisse. Ich kenne Arbeiten von Van Meter und anderen über Quantenaddition und modulare Exponentiation, aber die Prüfung ihrer Referenzen (ich habe diese Arbeit noch nicht gelesen) zeigt keinen Hinweis darauf, dass dort Montgomery-Methoden in Betracht gezogen werden.

Die einzige Referenz, die ich gefunden habe, um dies zu diskutieren, ist auf Japanisch, was ich leider nicht lesen kann, obwohl es anscheinend aus einem Konferenzbericht von 2002 stammt. Eine maschinelle Übersetzung liefert die unten angehängten Nuggets, die darauf hinweisen, dass möglicherweise etwas Nützliches vorhanden ist. Ich kann jedoch keinen Hinweis darauf finden, dass dies weiterverfolgt wurde, was mich zu der Annahme veranlasst, dass die Idee a) geprüft und dann b) verworfen wurde.

Quantenschaltung bei der Ausführung von Arithmetik Noboru Kunihiro

... In dieser Studie, die jedoch ein relativ großes Qubit erfordert, schlagen wir eine modulare Exponentierschaltung vor, deren Quantenberechnungszeit kurz ist. Montgomery-Reduktion [8] und rechte Binärmethode [9] In Kombination bilden sie eine Schaltung Ru. Reduktion Montgomery wird m zufällig als natürliche Zahl ausgewählt, mod 2m durch die Operation, führe die Restoperation If, mod n Operationen beim Eliminieren aus. Dies führt zu einer Verkürzung der Rechenzeit ...

Anwendung von 3.2 Montgomery Reduction Montgomery Reduction [8] ist wie folgt formuliert ... Dieser Algorithmus kann die korrekten Werte zurückgeben und kann einfach bestätigt werden. MR (Y) er fragt nach einem Gesetz 2m Polynome mit 2m Punkten sind wichtig und müssen nur durch geteilt werden. Darüber hinaus gibt es in Montgomery Reduction verschiedene Berechnungsmethoden .... Im Allgemeinen ist Reduction Montgomery keine Eins-zu-Eins-Funktion ...

... Die vorgeschlagene Methode verwendet eine rechtsbinäre Methode, Montgomery Reducton hat eine Funktion, die übernommen wird. Als herkömmliches Verfahren zeichnet sich eine kleine Komponente der Schaltung aus. Qubit-Fehler, die viele Erwartungen haben müssen, können in weniger Rechenzeit berechnet werden. Die zukünftige Montgomery-Reduktions- und Steuerschaltung wird vom Qubit NICHT speziell beschrieben, was wirklich benötigt wird. Darüber hinaus nutzt jede Forschungsergebnisse, mehr als modulare Exponentiation, nicht-arithmetische (euklidische gegenseitige Teilung usw.) auch in Bezug auf die geplante Konfiguration einer effizienten Quantenschaltung.

... [8] PL Montgomery, "Modulare Multiplikation ohne Versuchsabteilung", Mathematics of Computation, 44, 170, S. 519-521, 1985 ...

S Jäger
quelle
1
Auf MO gekreuzt
S Huntsman
1
Sie haben nur eine Stunde vor dem Crossposting gewartet . Dies widerspricht unserer allgemeinen Richtlinie zum Crossposting: meta.cstheory.stackexchange.com/questions/225/… . Wir werden möglicherweise nur langsam antworten, aber eine Stunde scheint eine kurze Wartezeit zu sein, es sei denn, Sie haben es WIRKLICH eilig.
Suresh Venkat
Diese Richtlinie war mir leider nicht bekannt. Ich entschuldige mich - ich verspreche, die FAQ (erneut) zu lesen. Gib mir eine Gegenstimme.
S Huntsman
Ich gebe Ihnen eine Gegenstimme, wenn Sie eine so natürliche Frage stellen.
Ross Snider
7
Mir ist nicht klar, ob irgendjemand überhaupt die Zeit investiert hat, um festzustellen, ob es ein Hindernis gibt, die Quantenfaktorisierung mithilfe der Montgomery-Exponentiation zu beschleunigen. Gute Frage.
Peter Shor

Antworten:

10

Könnten Sie den originalen japanischen Titel / Referenz posten?

Sie könnten auch überlegen, nur an den Autor zu schreiben - vorausgesetzt, er ist derselbe Professor an der Universität von Tokio:

http://www.it.ku-tokyo.ac.jp/~kunihiro/

und würde mit ziemlicher Sicherheit antworten.

Tut mir leid, dies als Antwort zu posten, es sollte ein Kommentar sein, aber ich habe anscheinend noch keinen Repräsentanten dafür ...

EDIT: Also habe ich mir das Original Japanisch angesehen. Als Vorwort bin ich derzeit Doktorandin in der EE-Abteilung der Universität Tokio, ursprünglich aus den USA, und ich mache technische JA-> EN-Übersetzungen als Teilzeitjob. Dieser Themenbereich liegt jedoch weit außerhalb meiner Komfortzone. Bitte nehmen Sie meine Meinung mit einem Körnchen Salz!

Grundsätzlich lautet die Schlussfolgerung (4):

べ べ き 乗 き き き き き き き き き き き き き き き き き き き き っ っ っ き き き き っ。。。。。。。。。。。。。。。。。。。 と と。。。。

[In diesem Artikel] Wir haben eine neue Quantenschaltung für die Berechnung der modularen Exponentiation vorgeschlagen. Das vorgeschlagene Verfahren verwendet ein binäres LR-Verfahren und ist auch durch die Verwendung der Montgomery-Reduktion gekennzeichnet. Im Vergleich zu früheren Verfahren erfordert das vorgeschlagene Verfahren weniger Komponenten, um die Schaltung aufzubauen. Das vorgeschlagene Verfahren hat jedoch den Nachteil, dass eine große Anzahl von Qubits erforderlich ist, wir sind jedoch zuversichtlich, dass es rechnerisch effizient sein wird (beleuchtet: erfordern sehr wenig Rechenzeit).

Ich habe versucht, in Englisch und Japanisch nach ähnlichen Folgepapieren zu suchen, war aber erfolglos. Ich vermute, dass der Ansatz erfolglos war oder der Professor mit etwas anderem beschäftigt war (es sieht so aus, als hätte er die Universität gewechselt).

Ich denke, dass Ihre beste Wahl zu diesem Zeitpunkt ist, Professor Kunihiro direkt zu schreiben (auf Englisch!), Vorausgesetzt, Sie möchten den Rest des Weges weiterverfolgen und eine konkrete Antwort erhalten.

s8soj3o289
quelle
Cripes, ich dachte, ich hätte diesen Link in die ursprüngliche Frage eingefügt. Anscheinend nicht: scholar.google.com/scholar?cluster=14809499008269761518
S Huntsman
Link zur ursprünglichen Frage hinzugefügt. Ich habe seine Website gesehen, so habe ich mir das aus einem Verfahren von 2002 vorgestellt.
S Huntsman
5
Es scheint mir, dass das Gleiche schief gelaufen ist, was beim schnellen Multiplikationsalgorithmus von Karatsuba schief gelaufen ist: Um es reversibel zu machen, scheint es erforderlich zu sein, eine große Anzahl zusätzlicher Qubits (dh Speicherplatz oder Speicher) zu verwenden. Eine gute Forschungsfrage ist, ob dies unvermeidlich ist oder nicht. Danke für die Übersetzung.
Peter Shor
2
Das Umkehren bestimmter Berechnungen kann viel zusätzlichen Speicherplatz erfordern. Dieses Problem wird hier behandelt.
Peter Shor
1
@blackkettle: Um festzustellen, ob die Erweiterung des Weltraums unvermeidbar ist, sind in der theoretischen Informatik neue Beweistechniken für niedrigere Schranken erforderlich. Daher ist es sehr unwahrscheinlich, dass dies bald der Fall sein wird. Was passieren könnte, ist die Suche nach einer platzsparenderen Methode zur modularen Potenzierung von Montgomery.
Peter Shor
3

Ich habe mich auch über diese Frage gewundert, da die gegenwärtigen Ansätze zur modularen Multiplikation für das Quantenfaktoring entweder eine Versuchssubtraktion verwenden, wenn es nach jeder Addition einen Überlauf gibt, oder einen Divisions- / Subtraktionsansatz am Ende. Beide scheinen verschwenderisch.

Ich arbeite an einer Quantenarchitektur für die Durchführung von Modexp mithilfe der Montgomery-Multiplikation. Ich denke nicht, dass der Platzaufwand größer sein sollte als bei früheren Ansätzen, aber ich sehe derzeit keine Notwendigkeit, die Karatsuba-Multiplikation zu verwenden.

Die Montgomery-Multiplikation in Binärform ist sehr effizient (Bitverschiebung und Addition). Die Addition des Moduls und der verschobenen Summen hängt von dem niedrigstwertigen Bit (LSB) bei jedem Schritt ab, so dass dies seriell zu erfordern scheint, um O (n) -Zeit zu erhalten.

Sie können diese Abhängigkeit vom LSB jedoch parallelisieren, indem Sie Funktionstabellen verwenden und sie ähnlich wie Carry-Lookahead-Ansätze oder Kitaevs Beschreibung paralleler endlicher Automaten in seinem Buch zusammenstellen / eingrenzen (Kitaev, Shen, Vyalyi 2002). Dieser Schritt erfordert mit ziemlicher Sicherheit eine Menge Ancillae, kann jedoch asymptotisch zu einer O (log n) -Tiefe gemacht werden.

Paul Pham
quelle