Como hemos visto la dificultad matemática esencial de la descriptación de un mensaje en el sistema RSA consiste en la imposibilidad, hoy por hoy, de factorizar un número N de, por ejemplo, 100 dígitos.

Si tratamos de efectuar la factorización por el camino tradicional de un número N de L dígitos, esto nos lleva a la realización de un número de divisiones que aproximadamente es de 10^(L/2), es decir (un crecimiento exponencial con L).

Supongamos que N es de L= 100 dígitos y que disponemos de un ordenador que hace 10^10 divisiones por segundo. El ordenador tardará en factorizar N por el método tradicional  aproximadamente 10^50/10^10=10^40 segundos. Demasiado tiempo ya que la edad estimada del universo es de 3,8*10^17 segundos (12.000 millones de años)

En el sistema RSA esto nos lleva a tratar de resolver la ecuación en r

Resolver a^r=1 (mod N) es equivalente a hallar el período de la función en x

Pero si se logra obtener r, resulta que en el caso que nos ocupa N es el producto de MCD(N,a^(r/2)+1) y MCD(N,a^(r/2)-1).
***********************************************************
Veamos cómo se puede proceder en un ejemplo sencillo.
Tratamos de factorizar 15.
Escogemos un número entero entre 0 y 15, por ejemplo 7. Lo elevamos a 1,2,3,4,...,14 sucesivamente y hallamos el resto de la división de estos números por 15. Resulta

Si para un N de 300 cifras pudiéramos elevar cada número 1,2,3,4,...,N-1 y hallar su resto al dividir el resultado por N...

Para la tarea efectuada del modo secuencial clásico se necesita demasiado tiempo, pero no para el ordenador cuántico.

Con el ordenador cuántico el tiempo de cálculo no crece exponencialmente con el número de dígitos L de N sino como una potencia cuadrática de L y así la tarea de factorizar un número de 300 cifras es cuestión de menos de un segundo. ¿Cómo lo hace?

El ordenador clásico acepta como entrada números de uno en uno y los va tratando de forma secuencial.

El ordenador cuántico puede aceptar como entrada una superposición coherente de muchos números y los puede tratar todos ellos simultáneamente.
***********************************************************

Un bit cuántico (qubit) es un sistema cuántico de dos estados posibles.
Un registro cuántico es un conjunto de un cierto número de qubits.
Consideramos dos registros cuánticos.
Tomamos el primer registro y lo situamos en superposición cuántica de todos los números enteros que contiene

Supongamos que el primer registro tiene dos qubits. Después de esta primera operación el registro estará en superposición de los cuatro números que puede contener

Realizamos a continuación una operación aritmética que utiliza el paralelismo cuántico calculando la función F(x)=a^x (mod N) para cada número x en la superposición.
Los valores de F(x) se colocan entonces en el segundo registro de modo que después de este calculo los dos registros aparecen enmadejados (entangled)

A continuación realizamos una medición del segundo registro. Tal medición nos proporciona un valor aleatorio de F(k) para algún k. El estado del primer registro después de la medición efectuada en el segundo, debido a la periodicidad de F(x), es una superposición coherente de todos los estados 
tales que x=k,k+r,k+2r,..., es decir para los x tales que F(x)=F(k). Como el valor k es seleccionado aleatoriamente en la medición resulta que el estado del primer registro es transformado mediante una operación unitaria
que lleva k a 0 (es decir  se convierte en  más un factor de fase) y modifica el período de r a un múltiplo de 1/r (transformada de Fourier cuántica).

Ahora se hace una medición en el primer registro que proporciona la mejor aproximación a un múltiplo de 1/r. Se calculan así r y los factores de N como se ha indicado antes.

Muchos piensan que esto es un obstáculo insalvable, ya que la coherencia del sistema cuántico se pierde con la observación. Pero esta dificultad se está atacando mediante métodos diversos de los que se puede esperar que conduzcan al momento en que la construcción de un ordenador cuántico sea una realidad.

Criptología

       D. Welsh, Codes and Cryptography (Clarendon Press, Oxford, 1988).
       B. Schneier, Applied cryptography: protocols, algorithms, and source code  in C.,(John Wiley & Sons, New York 1994).
       G. Brassard, Modern Cryptology: A Tutorial, (Springer, Berlin 1988).
       D.E. Denning, Cryptography and Data Security, (Addison-Wesley,1982).

Computación cuántica

        D. Deutsch, 1985, Proc. R. Soc. London, Ser. A: 400, 97.
       D. Deutsch, 1989, Proc. R. Soc. London, Ser. A: 425, 73.
       D. Deutsch and R. Jozsa, 1992, Proc. R. Soc. London, Ser A: 439, 553.
       R. Jozsa, 1991, Proc. R. Soc. London, Ser. A: 435, 563.
 

Las referencias principales:

       P.W. Shor, ``Algorithms for quantum computation: Discrete logarithms and factoring'', in Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, edited by S. Goldwasser (IEEE Computer Society Press, Los Alamitos, CA), pages 124-134 (1994).
       P.W. Shor, ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer'', SIAM J. Computing 26, pages 1484-1509 (1997).