Factorización polinomial de números enteros J. García-López - U.P.M. (Grupo de Computación Cuántica) TECHNICAL REPORT Nº 21 Diciembre 2003

Jesús García López de Lacalle Dep. Matemática Aplicada. E.U. Informática. U.P. Madrid Ctra. de Valencia Km.7, 28031 Madrid, España e_mail: [email protected]

Departamento de Matemática Aplicada E.U. Informática. U. Politécnica Madrid Ctra. de Valencia Km. 7 28031 Madrid, España

Factorizaci´ on polinomial de n´ umeros enteros∗ Jes´ us Garc´ıa L´opez de Lacalle† 4 de diciembre de 2003

1

Introducci´ on

En este art´ıculo presentamos el algoritmo polinomial de factorizaci´on de n´ umeros enteros obtenido por Peter W. Shor [18] en 1994. Se trata del resultado m´as prometedor del modelo cu´antico de computaci´on desarrollado en los u ´ltimos a˜ nos. Este resultado rompe te´oricamente uno de los protocolos criptogr´aficos de clave p´ ublica m´ as importantes, el protocolo RSA. Afortunadamente, el propio modelo de computaci´on cu´antica permite la implementaci´ on de protocolos criptogr´aficos de clave privada seguros. La computaci´on cu´ antica empez´ o a desarrollarse en la d´ecada de los ochenta a ra´ız de las propuestas de Paul Benioff, David Deutsch y Richard Feynman. En 1982 Benioff [1] y Feynman [9] sugirieron independientemente que, dado el elevado coste computacional del c´alculo de la evoluci´on de sistemas cu´anticos, la evoluci´ on de estos sistemas se podr´ıa considerar como una herramienta de c´alculo m´as que como un objeto a calcular. Poco despu´es, en 1985, y tambi´en de forma independiente Deutsch [7] propone la b´ usqueda de un ordenador que sea capaz de simular eficientemente un sistema f´ısico arbitrario. La conjunci´on de todas estas ideas ha conducido a la concepci´on actual de ordenador cu´antico. Cuestionar el sistema de computaci´ on cl´asico, que cuenta con una s´olida base te´orica y con el aval de infinidad de aplicaciones en todos los ´ ambitos de la vida cotidiana, s´olo tiene sentido si el modelo que se propone como alternativo es potencialmente mejor que el actual. Efectivamente as´ı lo hacen Benioff, Deutsch y Feynman, fundamentando sus propuestas sobre la posibilidad de que los sistemas cu´anticos tengan mayor potencia de c´ alculo que los cl´asicos. El argumento que todos utilizan para apuntar esta posibilidad es el hecho de que la simulaci´ on de un ordenador cu´antico (sistema cu´antico) en un ordenador cl´asico requiere una gran cantidad de operaciones. El principal m´etodo para aumentar la capacidad de c´alculo de un ordenador cl´asico es el procesamiento en paralelo. Los ordenadores que soportan este esquema de programaci´on disponen de varios cientos o miles de procesadores. Sabemos que la capacidad de almacenamiento de informaci´on y la capacidad de c´alculo de un ordenador son proporcionales al n´ umero de celdas de memoria y al n´ umero de procesadores respectivamente, es decir, al tama˜ no del ordenador. Entonces la capacidad de un ordenador cl´asico (de almacenamiento y de c´ alculo) crece linealmente con respecto a su tama˜ no. En un ordenador cu´ antico la situaci´ on cambia por completo, hasta el punto que su capacidad crece exponencialmente con respecto a su tama˜ no. Este hecho, estrechamente relacionado con el principio de superposici´ on de la mec´ anica cu´ antica, se denomina paralelismo cu´antico. Llamamos qubits o bits cu´anticos a los sistemas cu´ anticos elementales, es decir, a los sistemas cu´anticos de dos estados. Los sistemas cu´anticos de n qubits se describen mediante vectores de un espacio de Hilbert complejo de dimensi´on 2n . Esto permite codificar una cantidad exponencial de informaci´on en el estado de un sistema cu´antico de n qubits. Adem´ as, cualquier tranformaci´on del estado del sistema se traduce en la modificaci´on simult´ anea de toda la informaci´ on almacenada. Por tanto, la capacidad de un ordenador cu´antico (tanto de almacenamiento como de c´ alculo) crece exponencialmente con respecto a su tama˜ no. Sin embargo, la medici´ on de estados cu´anticos es un inconveniente importante para la computaci´on cu´antica. Hay que recordar que las medidas cu´anticas no son deterministas. Esto quiere decir, por ∗ Este † Dep.

trabajo ha sido subvencionado por el MCYT, proyecto TIC2002-01541. de Matem´ atica Aplicada, Escuela U. de Inform´ atica, U. Polit´ ecnica Madrid (http://www.upm.es/˜jglopez).

1

ejemplo, que si medimos dos estados iguales los resultados no tienen por qu´e ser iguales. El proceso de medida es, por tanto, un experimento aleatorio en el que la probabilidad de cada resultado est´a determinada por el estado del sistema. Las dificultades para sacar provecho del paralelismo cu´antico son tan notables que hubo que esperar m´as de una d´ecada para encontrar el primer gran resultado. En 1994 Peter W. Shor sorprendi´o a todos presentando sendos algoritmos polinomiales para factorizar n´ umeros enteros y para calcular logaritmos discretos [18]. Fue el primer problema en el que se alcanzaba una aceleraci´on exponencial con respecto a los mejores algoritmos cl´ asicos conocidos. A ra´ız de este descubrimiento se gener´o una gran actividad, tanto en el desarrollo de la tecnolog´ıa necesaria para la construcci´on de ordenadores cu´anticos como en el estudio de algoritmos cu´ anticos. El algoritmo de Shor rompi´ o te´ oricamente el sistema criptogr´afico m´as difundido en la actualidad, el sistema RSA propuesto por Rivest, Shamir y Adleman en 1978 [17]. Este hecho contribuy´o a su vez al desarrollo de los sistemas criptogr´ aficos cu´anticos [2]. Las t´ecnicas que se utilizan para garantizar la confidencialidad de los canales cu´ anticos se apoyan en una propiedad caracter´ıstica de la mec´anica cu´antica: los estados cu´ anticos no se pueden copiar (clonar) [23]. En el ´area de las comunicaciones, adem´as del estudio de la confidencialidad, se est´an investigando otros problemas como, por ejemplo, la codificaci´on de informaci´ on cl´ asica en canales cu´anticos y el teletransporte de estados cu´anticos. Sin embargo, el estudio de este modelo de computaci´on apenas si ha comenzado. Hasta el momento, s´olo se han desarrollado ordenadores cu´anticos basados en resonancia magn´etica nuclear [5, 11], en trampas de iones [4] y en cavidades cu´anticas [8]. Con la primera de estas t´ecnicas se han conseguido prototipos de hasta 10 qubits, sobre los que se ha probado el algoritmo de Shor. Tambi´en se ha propuesto la construcci´ on de ordenadores cu´anticos aprovechando los conocimientos actuales sobre semiconductores [15, 22], aunque esta t´ecnica est´a menos desarrollada. Desde el punto de vista algor´ıtmico, s´olo se ha podido hacer efectiva una ganancia exponencial en el c´alculo de transformadas de Fourier y, en estos momentos, ´esta es la herramienta m´as importante de la computaci´ on cu´ antica. Otra t´ecnica que permite mejorar la complejidad de algunos algoritmos cl´asicos, aunque con ganancia solamente cuadr´atica, es el m´etodo de Grover de b´ usqueda en conjuntos no estructurados [13]. Los ordenadores cu´ anticos, a diferencia de los cl´asicos, son dispositivos anal´ogicos. Este hecho plantea mayores dificultades para la construcci´ on de ordenadores cu´anticos que las que se tuvieron que afrontar para ordenadores cl´ asicos. En primer lugar, los estados cu´anticos se modifican por la influencia del entorno. Esto provoca el fen´ omeno denominado decoherencia que se convierte en una fuente de errores. Y, en segundo lugar, la imprecisi´ on del propio ordenador cu´antico al aplicar el algoritmo constituye una nueva fuente de errores. Estas son las razones fundamentales por las que la computaci´on cu´antica requiere un mecanismo para acotar la acumulaci´on de errores durante el proceso de c´alculo. Para ello hay que superar dificultades importantes: los errores cu´anticos son continuos, no se pueden copiar estados y, hasta el final, no se puede leer (medir) la informaci´on codificada en un estado cu´antico. Estos obst´aculos fueron finalmente superados, una vez que Shor [19] y Steane [20] establecieran las ideas b´asicas para la construcci´on de c´ odigos cu´ anticos y se formalizase de forma consistente la teor´ıa cu´antica de c´odigos [6, 12].

2

Modelo cu´ antico de computaci´ on

En computaci´ on cu´ antica la unidad elemental de informaci´on se denomina qubit y, del mismo modo que el bit cl´asico, se define a partir de dos estados b´asicos que se denotan |0i y |1i respectivamente. A diferencia de los bits, los qubits pueden estar en estados que son combinaci´on lineal de los dos estados b´asicos. Por ejemplo, √ 3 1 |1i (1) Ψ = |0i + 2 2 puede ser el estado de un qubit. Formalmente, un qubit es un vector unitario en el espacio de Hilbert complejo H generado por los vectores |0i y |1i que determinan una base ortonormal. En la pr´actica se trabaja con un conjunto de n qubits (un n−qubit), del mismo modo que en computaci´on cl´asica se trabaja con una cadena de n bits.

2

Cu´anticamente un n−qubit es un vector unitario del espacio de Hilbert complejo Hn = H ⊗ · · · ⊗ H en el que Bn = [ |0i ⊗ · · · ⊗ |0i ⊗ |0i, |0i ⊗ · · · ⊗ |0i ⊗ |1i, |0i ⊗ · · · ⊗ |1i ⊗ |0i, . . . , |1i ⊗ · · · ⊗ |1i ⊗ |1i ] es una base ortonormal, llamada base de computaci´on. Los vectores de la base Bn se pueden interpretar como cadenas de bits o como n´ umeros enteros: |k1 i ⊗ · · · ⊗ |kn i ≡ |k1 . . . kn i ≡ |ki, donde k es el n´ umero con representaci´ on binaria k1 . . . kn . Con esta notaci´on un n−qubit es un vector Ψ=

n 2X −1

ak |ki

tal que

k=0

n 2X −1

|ak |2 = 1

(2)

k=0

El proceso de c´ alculo se realiza sobre el n−qubit, que inicialmente est´a en estado |0i, mediante la aplicaci´on de una transformaci´ on unitaria. Sin embargo, no podemos suponer que un ordenador cu´antico vaya a ser capaz de aplicar una transformaci´on unitaria arbitraria. Es preciso descomponerla en un producto de transformaciones unitarias elementales (puertas cu´anticas), del mismo modo que en computaci´on cl´ asica una funci´ on booleana se descompone en un producto de puertas l´ogicas. Las puertas cu´anticas son transformaciones unitarias en H (puertas de un qubit) o en H2 (puertas de dos qubits). Entre las puertas cu´ anticas m´ as importantes para la construcci´on de algoritmos se incluyen las siguientes, 2πi siendo σk = e 2k :     |0i → |1i  |0i → |0i  |0i → √1 (|0i + |1i) 2 X: Rk : H:  |1i → |0i  |1i → σk |1i  |1i → √1 (|0i − |1i) 2

   |00i →      |01i → CX :  |10i →       |11i →

|00i |01i |11i |10i

   |00i →      |01i → CRk :  |10i →       |11i →

|00i |01i |10i σk |11i

   |00i →      |01i → S:  |10i →       |11i →

|00i |10i |01i |11i

La puerta X se puede interpretar como la negaci´on l´ogica, puesto que intercambia los estados |0i y |1i. Por tanto, CX (Controlled X) se puede ver como la negaci´on del segundo qubit si el primero est´a en estado |1i. La puerta Rk introduce el factor de m´odulo uno σk en el estado |1i y CRk (Controlled Rk ) hace lo mismo en el segundo qubit, si el primero est´a en estado |1i. Por u ´ltimo, la puerta S (Swap) intercambia los estados de los dos qubits y la transformaci´on H de Hadamard, aplicada a cada uno de los qubits, modifica el n−qubit, inicialmente en estado |0i, dando como resultado un estado mucho m´as interesante para la computaci´ on cu´ antica: Ψ = (H ⊗ · · · ⊗ H) (|0i ⊗ · · · ⊗ |0i) = (H|0i) ⊗ · · · ⊗ (H|0i) n

=

√1 2n

2 −1 1 X (|0i + |1i) ⊗ · · · ⊗ (|0i + |1i) = √ |ki 2n k=0

Esta transformaci´ on unitaria, W = H ⊗· · ·⊗H, recibe el nombre de tranformada de Walsh-Hadamard y es una de las herramientas m´ as importantes en el dise˜ no de algoritmos cu´anticos. Se puede calcular una expresi´on expl´ıcita de W |ki, para cualquier vector |ki de la base de computaci´on, en t´erminos de la forma bilineal sim´etrica (k|j) = (k1 j1 ) ⊕ · · · ⊕ (kn jn ) definida en el espacio vectorial (ZZ2n , ⊕, ZZ2 ): n

2 −1 1 X W |ki = √ (−1)(k|j) |ji 2n j=0

(3)

Una vez realizado el c´ alculo es preciso medir el n−qubit para obtener los resultados. Seg´ un los postulados de la mec´ anica cu´ antica una medida es un proceso aleatorio ligado a una suma ortogonal V0 ⊕ V1 ⊕ · · · ⊕ Vh . Durante el proceso de medida el n−qubit se proyecta ortogonalmente sobre uno de los subespacios. Si el estado del n−qubit es Ψ = α0 v0 + · · · + αh vh , donde vk es la proyecci´on ortogonal de Ψ en el subespacio Vk , 0 ≤ k ≤ h, la probabilidad de que la proyecci´on se produzca en el subespacio Vk es |αk |2 . Si durante este proceso el estado se proyecta sobre el subespacio Vk , entonces el estado final del 3

n−qubit ser´ a vk y diremos que el resultado de la medida ha sido k. Obs´ervese que una medida cu´antica, adem´as de no proporcionar un conocimiento completo del n−qubit, modifica su estado. Esta es, junto con la imposibilidad de copiar estados [23], la mayor dificultad con la que se enfrenta la computaci´on cu´antica. Tal como ocurre con las transformaciones unitarias, no podemos suponer que un ordenador cu´antico vaya a ser capaz de realizar una medida cu´antica arbitraria. Es preciso reducirla, mediante una transformaci´on unitaria (cambio de base), a una medida asociada a una suma ortogonal de subespacios generados por los vectores de la base de computaci´ on Bn y, a continuaci´on, descomponerla en un producto de medidas de qubits individuales. La suma ortogonal correspondiente a la medida de un qubit, por ejemplo el k−´esimo, es V0 ⊕ V1 , donde V0 y V1 est´an generados por todos los vectores de la base Bn en los que dicho qubit est´ a en estado |0i y |1i respectivamente. Por ejemplo, si en el estado 1 1 1 1 Ψ = √ |00i + √ |01i + √ |10i + √ |11i 42 7 3 2

(4)

medimos el primer qubit y, a continuaci´ on, el segundo qubit los resultados posibles son los que se muestran en las siguientes tablas. En la primera se detalla cada una de las medidas y en la segunda se dan los resultados de las dos medidas en conjunto: 1a

Prob.

0

5 6

q

1 6

q

1

2.1

Estado 3 5 |00i

6 7 |10i

+

+

q

2 5 |01i

√1 |11i 7

2a

Prob.

Estado

0

3 5

|00i

00

1 2

|00i

1

2 5

|01i

01

1 3

|01i

0

6 7

|10i

10

1 7

|10i

1

1 7

|11i

11

1 42

|11i

Medida Prob. Estado

Problema de Simon

Una de las primeras cuestiones que se resolvieron en computaci´on cu´antica, con ganancia exponencial respecto a los algoritmos cl´ asicos, fue el problema de Simon. En el espacio vectorial (ZZ2n , ⊕, ZZ2 ) una n funci´on booleana f : ZZ2 → ZZ2n es peri´ odica de periodo T ∈ ZZ2n si para todo k ∈ ZZ2n se cumple f (k ⊕ T ) = f (k) y es 2 a 1 si para todo k ∈ ZZ2n se cumple que f −1 (k) tiene cardinal 0 ´o 2. El problema consiste en determinar el periodo de f con el menor n´ umero posible de evaluaciones de la funci´on. En el modelo cu´ antico de computaci´ on en lugar de la funci´on f se utiliza la transformaci´on unitaria de 2n qubits Uf definida del siguiente modo: Uf (|ki ⊗ |ji) = |ki ⊗ |j ⊕ f (k)i

(5)

Desde el punto de vista cl´ asico hay que evaluar f sobre la mitad m´as uno de los elementos del dominio, es decir sobre 2n−1 + 1 elementos, para estar seguros de encontrar dos elementos k y j tales que f (k) = f (j). A partir de estos valores k y j se puede calcular el periodo de la funci´on: T = k ⊕ j. √ Si s´olo buscamos una soluci´ on probabil´ıstica, con cota de error , habr´ıa que evaluar la funci´on 2(n−1)/2 1 −  veces. Sin embargo, cu´ anticamente son suficientes O((n − 1) log(−1 )) evaluaciones. Los detalles de estos dos resultados se pueden ver en el ap´endice A. Algoritmo 1: 1. Inicializar el 2n−qubit Ψ = |0i ⊗ |0i. 2. Aplicar la transformada de Walsh-Hadamard W a los n primeros qubits. 3. Aplicar Uf . 4. Medir los n u ´ltimos qubits: j1 , . . . , jn (resultado j = j1 . . . jn ). 5. Aplicar de nuevo W a los n primeros qubits. 6. Medir los n primeros qubits: k1 , . . . , kn . Devolver k = k1 . . . kn . 4

El resultado final es un n´ umero entero k tal que (T |k) = 0. Para comprobarlo basta desarrollar el algoritmo paso a paso. La primera medida da como resultado cualquier valor de la imagen de f con probabilidad 2−n+1 , por ser una funci´ on 2 a 1, y la segunda cualquier valor k que cumple (T |k) = 0 tambi´en con probabilidad 2−n+1 . |0i ⊗ |0i

2

−−−−→ 4

−−−−→ 5

−−−−→ = 6

−−−−→

1 √ 2n

1 (|ki ⊗ |0i) −−−3−→ √ 2n 0≤k