¿Por qué no se considera la exponenciación modular de Montgomery para su uso en la factorización cuántica?

20

Es bien sabido que la exponenciación modular (la parte principal de una operación RSA) es computacionalmente costosa, y hasta donde yo entiendo, la técnica de exponenciación modular de Montgomery es el método preferido. La exponenciación modular también se destaca en el algoritmo de factorización cuántica, y también es costosa allí.

Entonces: ¿por qué la exponenciación modular de Montgomery aparentemente no está presente en las subrutinas detalladas actuales para la factorización cuántica?

Lo único que puedo imaginar es que hay una alta sobrecarga de qubit por alguna razón no obvia.

Ejecutar la "exponenciación modular" cuántica de Montgomery a través de Google Scholar no arroja resultados útiles. Soy consciente del trabajo de Van Meter y otros sobre la suma cuántica y la exponenciación modular, pero el examen de sus referencias (aún no he leído este trabajo) no muestra ninguna indicación de que los métodos de Montgomery se consideren allí.

La única referencia que he encontrado que parece discutir esto está en japonés, que lamentablemente no puedo leer, aunque aparentemente es de un acta de la conferencia de 2002. Una traducción automática produce pepitas agregadas a continuación que indican que podría haber algo útil. Sin embargo, no puedo encontrar ninguna indicación de que esto se haya seguido, lo que me hace pensar que la idea ha sido a) considerada y luego b) descartada.

Circuito cuántico en la realización de la aritmética Noboru Kunihiro

... En este estudio, pero requiere un qubit relativamente grande, proponemos un circuito de exponenciación modular que el tiempo de cálculo cuántico es corto. Reducción de Montgomery [8] y método binario derecho [9] Combinados, constituyen un circuito Ru. La reducción Montgomery es, m elegida aleatoriamente como un número natural, mod 2m por la operación, realiza la operación restante Si, mod n operaciones en eliminación. Esto conducirá a la reducción del tiempo de cálculo ...

Aplicación de 3.2 Reducción de Montgomery La reducción de Montgomery [8] se formula de la siguiente manera ... Este algoritmo puede devolver los valores correctos y puede confirmarse fácilmente. MR (Y) pide una ley 2m Los polinomios con 2m puntos son importantes y solo requieren división por. Además, Montgomery Reduction, hay diferentes métodos de cálculo ... En general, Reduction Montgomery no es una función uno a uno ...

... El método propuesto utiliza un método binario correcto, Montgomery Reducton tiene una característica que se adopta. Que el método convencional, caracterizado por tener un pequeño componente del circuito Have. La falla qubit que se requiere para tener muchas expectativas se puede calcular en menos tiempo computacional. El futuro, la reducción de Montgomery y los circuitos de control específicamente NO descritos por el qubit realmente necesarios. Evaluar el número se espera que evalúe el tiempo de cálculo. Además, cada uno aprovecha los resultados de la investigación, más que la exponenciación modular No aritmética (división mutua euclidiana, etc.) también con respecto a la configuración planificada de un circuito cuántico eficiente.

... [8] PL Montgomery, "Multiplicación modular sin división de prueba", Matemáticas de la computación, 44, 170, pp. 519-521, 1985 ...

S Huntsman
fuente
1
Crossposted to MO: mathoverflow.net/questions/46256
S Huntsman
1
Solo esperó una hora antes de la publicación cruzada, lo que va en contra de nuestra política general de publicación cruzada: meta.cstheory.stackexchange.com/questions/225/… . Puede que seamos lentos en responder, pero una hora parece ser un corto tiempo de espera, a menos que tenga mucha prisa.
Suresh Venkat
Lo sentimos, no estaba al tanto de esta política. Mis disculpas: prometo (re) leer las preguntas frecuentes. Dame un voto negativo.
S Huntsman el
Te daré un voto positivo por hacer una pregunta tan natural.
Ross Snider
77
No me queda claro si alguien se ha tomado el tiempo para determinar si existe algún obstáculo para acelerar la factorización cuántica utilizando la exponenciación de Montgomery. Buena pregunta.
Peter Shor

Respuestas:

10

¿Podría publicar el título / referencia japonés original?

Además, podría considerar escribir al autor, suponiendo que sea el mismo tipo con el que es profesor en la Universidad de Tokio:

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

y casi seguramente respondería.

Lamento publicar esto como respuesta, debería ser un comentario, pero aparentemente todavía no tengo el representante para eso ...

EDITAR: Entonces, eché un vistazo al japonés original. Como prefacio, actualmente soy estudiante de doctorado en el departamento de EE en U. Tokio, originario de los EE. UU., Y hago traducción técnica JA-> EN como trabajo a tiempo parcial. Sin embargo, esta área temática está muy fuera de mi zona de confort, ¡así que por favor tome mi opinión con un grano de sal!

Básicamente la conclusión (4) dice:

べ 、 、 べ Reduて い る 。qubit が 多 く 必要 と な る と い う 欠 点 は 持 つ が 、 よ り 少 な い 計算 時間 で 計算 が で き る と 期待 さ れ る。

[En este artículo] Propusimos un nuevo circuito cuántico para calcular la exponenciación modular. El método propuesto utiliza un método binario LR y también se caracteriza por el uso de la reducción de Montgomery. En comparación con los métodos anteriores, el método propuesto requiere menos componentes para construir el circuito. Sin embargo, el método propuesto tiene el inconveniente de requerir una gran cantidad de qubits, pero estamos seguros de que será computacionalmente eficiente (encendido: requiere muy poco tiempo de cálculo).

Traté de buscar documentos de seguimiento relacionados en inglés y japonés, pero no tuve éxito. Supongo que el enfoque no tuvo éxito, o el profesor se ocupó de otra cosa (parece que esto sucedió cuando cambió de universidad).

Creo que su mejor opción en este momento, suponiendo que quiera seguir el resto del camino y obtener una respuesta concreta, es escribir al profesor Kunihiro directamente (¡en inglés!)

s8soj3o289
fuente
Caramba, pensé que había pegado este enlace en la pregunta original. Aparentemente no: scholar.google.com/scholar?cluster=14809499008269761518
S Huntsman el
Enlace agregado a la pregunta original. He visto su sitio web, así es como pensé que era de un proceso de 2002.
S Huntsman
55
Me parece que lo mismo puede haber salido mal con el algoritmo de multiplicación rápida de Karatsuba: hacer que sea reversible parece requerir el uso de una gran cantidad de qubits adicionales (es decir, espacio o memoria). Una buena pregunta de investigación es si esto es inevitable o no. Gracias por la traducción.
Peter Shor
2
Hacer reversibles ciertos cálculos puede requerir mucho espacio extra; Este tema se discute aquí.
Peter Shor el
1
@blackkettle: determinar que la expansión del espacio es inevitable requeriría nuevas técnicas de prueba de límite inferior en informática teórica, por lo que es muy poco probable que esto suceda pronto. Lo que podría suceder es encontrar una forma más eficiente en el espacio de hacer la exponenciación modular de Montgomery.
Peter Shor el
3

También me preguntaba sobre esta pregunta, ya que los enfoques actuales de la multiplicación modular para la factorización cuántica usan una resta de prueba si hay un desbordamiento después de cada suma, o un enfoque de división / resta al final. Ambos parecen un desperdicio.

Estoy trabajando en una arquitectura cuántica para realizar modexp usando la multiplicación de Montgomery en este momento. No creo que la sobrecarga de espacio deba ser mayor que los enfoques anteriores, pero no veo la necesidad de usar la multiplicación de Karatsuba actualmente.

La multiplicación de Montgomery en binario es bastante eficiente (desplazamiento de bits y suma). La adición del módulo y las sumas desplazadas dependen del bit menos significativo (LSB) en cada paso, por lo que esto parece requerir ante ellos en serie, para obtener el tiempo O (n).

Sin embargo, puede paralelizar esta dependencia con el LSB utilizando tablas de funciones y componiéndolas / reduciéndolas de manera similar a los enfoques de anticipación o la descripción de Kitaev de autómatas finitos paralelos en su libro (Kitaev, Shen, Vyalyi 2002). Es casi seguro que este paso requiere muchos complementos, pero asintóticamente podría hacerse con profundidad O (log n).

Paul Pham
fuente