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 ...
Antworten:
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):
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.
quelle
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.
quelle