Pourquoi l'exponentiation modulaire de Montgomery n'est-elle pas envisagée pour une utilisation dans l'affacturage quantique?

Il est bien connu que l'exponentiation modulaire (la partie principale d'une opération RSA) est coûteux en calcul, et pour autant que je comprends les choses, la technique d' exponentiation modulaire de Montgomery est la méthode préférée. L'exponentiation modulaire est également mise en évidence dans l'algorithme d'affacturage quantique, et elle est également coûteuse.

Alors: pourquoi l'exponentiation modulaire de Montgomery n'est-elle pas apparemment présente dans les sous-programmes détaillés actuels pour l'affacturage quantique?

La seule chose que je peux imaginer, c'est qu'il y a un surdébit de qubit élevé pour une raison non évidente.

L'exécution de "l'exponentiation modulaire" quantique de montgomery via Google Scholar ne donne aucun résultat utile. Je connais les travaux de Van Meter et d'autres sur l'addition quantique et l'exponentiation modulaire, mais l'examen de leurs références (je n'ai pas encore lu ce travail) ne montre aucune indication que les méthodes de Montgomery y sont envisagées.

La seule référence que j'ai trouvée qui semble en discuter est en japonais, que je ne peux malheureusement pas lire, même si apparemment elle provient d'une conférence de 2002. Une traduction automatique donne des pépites ajoutées ci-dessous qui indiquent qu'il pourrait y avoir quelque chose d'utile. Cependant, je ne trouve aucune indication que cela ait été suivi, ce qui me fait penser que l'idée a été a) examinée puis b) rejetée.

Circuit quantique dans l'exécution de l'arithmétique Noboru Kunihiro

... Dans cette étude, mais nécessite un qubit relativement important, nous proposons un circuit d'exponentiation modulaire dont le temps de calcul quantique est court. Montgomery Reduction [8] et méthode binaire droite [9] Combinés, ils constituent un circuit Ru. Réduction Montgomery est, m choisi au hasard comme un nombre naturel, mod 2m par l'opération, effectuer l'opération restante Si, mod n opérations en éliminant. Cela entraînera une réduction du temps de calcul ...

Application de la réduction de Montgomery 3.2 La réduction de Montgomery [8] est formulée comme suit ... Cet algorithme peut renvoyer les valeurs correctes qui peuvent être facilement confirmées. MR (Y) il demande une loi 2m Les polynômes avec 2m points sont importants et ne nécessitent qu'une division par. De plus, Montgomery Reduction in, il existe différentes méthodes de calcul .... En général, Reduction Montgomery n'est pas une fonction biunivoque ...

... La méthode proposée utilise une bonne méthode binaire, Montgomery Reducton a une caractéristique qui est adoptée. Que la méthode conventionnelle, caractérisée par une petite composante du circuit Have. la faute qubit qui doit avoir beaucoup d'attentes peut être calculée en moins de temps de calcul Be. L'avenir, Montgomery Réduction et circuits de contrôle spécifiquement NON décrits par le qubit vraiment nécessaire Évaluer le nombre devrait évaluer le temps de calcul. En outre, chacun tirant parti des résultats de la recherche, plus que l'exponentiation modulaire non arithmétique (division mutuelle Euclide, etc.) également en ce qui concerne la configuration prévue d'un circuit quantique efficace.

... [8] PL Montgomery, «Modular Multiplication Without Trial Division», Mathematics of Computation, 44, 170, pp. 519-521, 1985 ...

Pourriez-vous publier le titre / référence japonais d'origine?

En outre, vous pourriez envisager d'écrire à l'auteur - en supposant que c'est le même gars qu'il est professeur à l'Université de Tokyo:

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

et répondrait presque certainement.

Désolé de poster ceci comme réponse, ce devrait être un commentaire mais je n'ai pas encore de représentant pour ça apparemment ...

EDIT: Donc, j'ai jeté un œil au japonais d'origine. En préface, je suis actuellement doctorant au département EE à U. Tokyo, originaire des États-Unis, et je fais de la traduction technique JA-> EN comme travail à temps partiel. Cependant, ce sujet est bien en dehors de ma zone de confort, alors prenez mon avis avec un grain de sel!

Fondamentalement, la conclusion (4) dit:

Méthode binaire を 採用 剰 行 行 行 い い と い い い 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 、 て て て て て て て て て て て て て て て て て て て て て て て て てて い る 。qubit が 多 く 必要 と な る と い う 欠 点 は 持 つ が 、 よ り 少 な い 計算 時間 で 計算 が で き る と 期待 さ れ る。

[Dans cet article] Nous avons proposé un nouveau circuit quantique pour calculer l'exponentiation modulaire. La méthode proposée utilise une méthode binaire LR et se caractérise également par l'utilisation de la réduction de Montgomery. Par rapport aux méthodes précédentes, la méthode proposée nécessite moins de composants pour construire le circuit. La méthode proposée a cependant l'inconvénient de nécessiter un grand nombre de qubits, mais nous sommes convaincus qu'elle sera efficace en termes de calcul (allumée: nécessite très peu de temps de calcul).

J'ai essayé de rechercher des documents de suivi connexes en anglais et en japonais, mais sans succès. Je suppose que l'approche s'est avérée infructueuse ou que le professeur s'est occupé d'autre chose (on dirait que c'était autour de lui lorsqu'il a changé d'université).

Je pense que votre meilleur pari à ce stade, en supposant que vous voulez suivre le reste du chemin et obtenir une réponse concrète, est d'écrire directement au professeur Kunihiro (en anglais!)

Je me suis également interrogé sur cette question, car les approches actuelles de la multiplication modulaire pour l'affacturage quantique utilisent soit une soustraction d'essai s'il y a un débordement après chaque ajout, soit une approche de division / soustraction à la fin. Ces deux éléments semblent inutiles.

Je travaille sur une architecture quantique pour effectuer le modexp en utilisant la multiplication de Montgomery en ce moment. Je ne pense pas que la surcharge d'espace devrait être plus grande que les approches précédentes, mais je ne vois pas la nécessité d'utiliser la multiplication de Karatsuba actuellement.

La multiplication de Montgomery en binaire est assez efficace (décalage de bits et addition). L'ajout du module et des sommes décalées dépend du bit le moins significatif (LSB) à chaque étape, donc cela semble nécessiter devant eux en série, pour obtenir le temps O (n).

Cependant, vous pouvez paralléliser cette dépendance vis-à-vis du LSB en utilisant des tables de fonctions et en les composant / en les rétrécissant de la même manière que les approches de portage ou la description par Kitaev des automates finis parallèles dans son livre (Kitaev, Shen, Vyalyi 2002). Cette étape nécessite presque certainement beaucoup d'ancillages, mais asymptotiquement, elle pourrait être réalisée en profondeur O (log n).