RSA v/s DSA

[Alvaro Herrera]

On Thu, Jun 03, 2004 at 04:04:13PM -0400, Claudio Baeza Retamal wrote:
> El problema es saber si una maquina cuantica sera determinista, en el
> sentido de que para un mismo problema siempre de la misma solucion, que
> para un mismo problema, los tiempos de resolucion esten acotados (en el
> sentido que si para un problema se demoro 2 segundos en resolverlo, en
> otro intento para el mismo problema no se demore 1 hora), cosas
> basicas que esperamos de un computador.

No, precisamente el punto de un computador cuantico es que es no
deterministico: la idea es poder resolver problemas NP en tiempo P (no
importa si el tiempo de ejecucion varian de una ejecucion a otra).

Un problema NP(*) es aquel que "resuelves en tiempo no polinomial en un
computador deterministico" (donde "tiempo no polinomial" significa que
el tiempo que necesitas para resolverlo crece exponencialmente segun el
taman~o de los datos del problema).  En un computador no deterministico
los puedes resolver en tiempo polinomial.  Ejemplo de esto es la
solucion del problema del vendedor viajero usando una jugarreta con
moleculas de ADN llamada "reaccion en cadena de la polimerasa" (PCR).
Un computador cuantico no es muy diferente en este sentido.  La
factorizacion es un problema de este tipo.

Y ojo, aqui decimos "computador cuantico" y a lo que nos estamos
refiriendo es a una solucion (i.e. un liquido con algunas porquerias
flotando) de determinadas moleculas a las que se les aplica tal y tal
estimulo y los resultados se leen de tales y tales maneras
(espectrografia, cromatografia, ionizacion, fluorescencia, que se yo).
No es una caja con un teclado y una pantalla.

(*) la clasificacion de problemas tiene mucha terminologia que
desconozco; NP-hard, co-NP, muchas otras; cada una tiene propiedades
particulares, la definicion que doy aqui es vaga.

-- 
Alvaro Herrera (<alvherre[a]dcc.uchile.cl>)
"People get annoyed when you try to debug them."  (Larry Wall)