edición general
145 meneos
963 clics
Factorización cuántica de números más rápida que el algoritmo de Shor

Factorización cuántica de números más rápida que el algoritmo de Shor

El algoritmo cuántico de Peter Shor permite factorizar un número de n dígitos binarios usando O(n) cúbits conectados por O(n2 log n) puertas lógicas cuánticas (operaciones individuales), finalizando con O(1) medidas cuánticas (ejecuciones repetidas) y un prostprocesado clásico en tiempo polinómico. Oded Regev publicó el año pasado en arXiv un nuevo algoritmo de factorización que requiere O(n3/2) puertas lógicas cuánticas, aunque con O(n3/2) cúbits, O(n1/2) medidas cuánticas y un nuevo postprocesado clásico en tiempo polinómico.

| etiquetas: factorización , cuántica , algoritmo , shor
Ojo con esto, que es peliagudo.

Lo digo en serio. Los sistemas de seguridad de datos en Internet se basan algoritmos cuya seguridad depende que la imposibilidad de factorizar números altos en un tiempo asumible.

Un algoritmo cuántico que pudiera factorizar números altos en tiempo asumible, podría "cargarse" la seguridad de las conexiones de Internet.

De todas formas, Francis ya avisa de que el algoritmo de factorización aún sigue siendo muy lento. Aunque este tipo de cosas debería…   » ver todo el comentario
#1 La segunda década de este siglo? Creo que estamos en la tercera...
#3 #1 Se ha corregido en el artículo.
"Pero que nadie se engañe, factorizar números de interés en criptografía y seguridad informática no se logrará hasta la segunda mitad de este siglo."
#19
La tercera, como bien dijo #3

Del 2001 al 2010 es la primera década del siglo XXI.

Del 2011 al 2020 es la segunda década.

Del 2021 al 2030 es la tercera década de este siglo.

Estamos en "los años 20" del siglo XXI, que es la tercera década... salvo el matiz de que "años 20" puede entenderse que empieza en 2020 y acaba al final de 2029, mientras que la tercera década empieza el 1 de enero de 2021 y acaba el 31 de diciembre de 2030.

Obviamente se trata de un…   » ver todo el comentario
#20
Quise decir
"antes de que llegue la tecnología de computadores cuánticos que rompen claves públicas"
(sean RSA, de curvas elípticas, o al parecer cualquier otra clave pública).
#21 estaba escribiendo que la curva elíptica usa logaritmos discretos en lugar de factorización y debería ser más difícil, pero veo en la wiki que también hay algoritmos cuánticos eficientes aunque no para todos los grupos de números. ( Se usa matemática modular aquí)
Así que te diría que de momento estamos protegidos, los algoritmos de curva elíptica están disponibles en prácticamente todos los sistemas, solo hay que seleccionarlos en la configuración.
#3 y la decada 0? ?(
#1

"De todas formas, Francis ya avisa de que el algoritmo de factorización aún sigue siendo muy lento."


No, no dice eso.
No es cuestión de lentitud.
Es cuestión de qubits... y de ruido.


Para factorizar un número de 2048 bits, como una clave RSA, se ha estimado que necesitarían unos 20 millones de cúbits físicos de este año 2024 para simular los aproximadamente 4096 cúbits lógicos.

¿Por qué tantos millones de cúbits físicos de los de 2024? Por el ruido…   » ver todo el comentario
#16 Me has recordado al chiste de :
Profesor: ¡Juanito rápido! dime cuánto es 2+2
Juanito: 5!
Profesor: Pero hombre Juanito, 2+2 son 4.
Juanito: Pero vamos a ver, usted qué quería... ¿Rapidez o precisión?
#29

Sí, a ese tipo de chiste me refería jajaja

El Principio de Incertidumbre de Heisenberg va de eso... Si tienes mucha precisión en la velocidad (o el momento lineal) tendrás poca en la posición y viceversa.
#16 Heisenberg nunca dejará de sorprenderme, lo mismo cocina meta azul como se marca un principio de incertidumbre

Vaaaaale, ya cierro al salir :-)
#16 quizá esté pecando de iluso, pero digo yo:

Si algo está cifrado con claves de 2048 bits, si en un futuro los ordenadores cuánticos pueden llegar a desencriptarlo (entiendo que no demasiados mensajes tienen la suficiente importancia como para reservar tiempo de proceso cuántico de este nivel), pues estas comunicaciones se pueden pasar a claves de 65536 bits, no? (o de 1048576 bits, si nos ponemos chulos)

Por tiempo de proceso, estos cifrados no son prácticos para aplicacions del público general, pero seguro que para comunicaciones de grado militar no debería haber problema, no?
#27

Esto suele tratar de cifrado asimétrico: claves públicas y privadas.
--> Breve introducción: tienes que comunicarte con banco, o pagar en Amazon, usas la clave pública del banco para enviarle una clave simétrica... Solo el banco puede leerlo con su clave privada (a menos que con cuántica sepas la privada a partir de la pública.
Nota: sin este cifrado asimétrico de clave pública no habría forma de comunicarse de forma segura con el banco... a menos que te diera en

…   » ver todo el comentario
#28 si, si, te entendido bien
No había tenido en cuenta la dificultad de buscar primos tan grandes

De todas formas, ahora le he dado una vuelta: para aplicaciones militares no hay mucho problema de hecho, porque para comunicaciones críticas se usan claves de 1 sólo uso.
El submarino y la base tienen una libro de claves, y en cada comunicación usan 1 de ellas. Aparte de usar una combinación de algoritmos de cifrado (como se hacía en TrueCrypt)
#1 Ya estamos en la segunda década de este siglo.
#19 tercera
#23 Cierto.
#1 Un poco de tranquilidad. "Aún así, factorizar números de interés en la criptografía actual, como RSA-2048 de 2048 bits, está más allá de lo concebible en las próximas décadas, tanto con el algoritmo de Shor, como con los dos nuevos algoritmos." Y eso hablando del algoritmo por qué si hablamos de la tecnología... En la algoritmia de la computación cuántica se aplican cosas que ni existen aún cono qbits ideales o de alta calidad.
#1 Ya se está trabajando en ello, y mucho, mirate todo lo que hay en Criptografía Post-Cuantica.

Las agencias e instituciones tienen preocupación en que alguien pueda guardar los datos hoy, y descifrar todo años más tarde cuando los ordenadores cuánticos estén más avanzados. Por eso, cuanto antes se implementen criptografías post-cuanticas, mas tranquilos estarán las agencias (sus secretos estarán a salvo).
#14 en los ultimos documentos a los que he tenido acceso, lo que se recomienda para cifrado de documentos es AES. La razón es que es un algoritmo de cifrado simétrico, por lo que no es susceptible de romperse por avances en la factorización de numeros primos.
#1 negativo por asustaviejas. Te has quedado anticuado. La solución ya existe: ECDSA
#1 Independientemente del algoritmo, la rapidez del procesamiento, puede romper las barreras de las contraseñas.

De todas formas, el tema a nivel personal, existe miles de soluciones. Por ejemplo, la localización + la huella del móvil + la huella de la persona + rostro. Es individual. En otros temas talvez.
#1 Siempre nos quedarán los algoritmos de cifrado basados en curvas elípticas, en lugar de números primos
Gracias por el envío #0 una explicación clara, concisa y muy esclarecedora, así da gusto entrar en MNM
#2 Es lo menos que podia hacer tras tu brillante envio de ayer.
Una exquisitez.
#2 Entrar en meneame, ir a pendientes, candidatas y desplazarte por 20 noticias para encontrarla :roll:

Acabas antes yendo a la fuente ... O que meneame linkee automaticamente todo lo que publique la mula francis en la seccion de ciencia ...
#2 Vale, tu comentario tiene más gracia una vez leído el artículo, aunque no me queda claro si has entendido lo mismo que yo.
Duda que tampoco despeja tras leer el artículo que comenta Ripio.
Algun día se sabrá la verdad.¬¬

#7 Es un comentario absurdo.
Entre el calor, y el agobio de esta noticia, creo que no voy a poder dormir hoy :troll:
old.meneame.net/search?q=algoritmo+de+shor

Y para colmo seguramente esto no lo entiende ni quien la puso
#9 Eso, aparte de no tener sentido, no invalida el envío, no entiendo un comentario tan negativo para un buen artículo.
Aquí la gente haciendo como que entiende algo de la noticia o_o
#10 Alguno habrá que la entienda.
#11 O(no) 8-D
A ver si alguien sube un tweet donde lo expliquen con un vídeo de 10 segundos bailando, porque así no hay manera.
Quizás conviene resaltar que el número más grande que se ha factorizado con el algoritmo de Shor en un ordenador cuántico ha sido 21 = 7 × 3 en el año 2012. En 2019 se intentó factorizar el número 35 = 7 × 5 con dicho algoritmo en un ordenador cuántico IBM Q System One (20 cúbits), pero fue imposible pues no tenía suficiente volumen cuántico

Pues parece que nuestras claves van a serguir seguras un tiempo. Aunque tampoco nos confiemos porque de un día para otro esto evoluciona exponencialmente.
Si te pones vizco, sale un delfín en la imagen. Aunque es mejor acercarse la imagen a los ojos y luego alejándola que es como sale correcta. Pero el lado oscuro es más rápido y tentador para conseguir poder (pero ves la imagen al revés de dentro afuera).
Era hora!!!! Ahora si voy a poder acelerar todos estos procesos tediosos a los que estoy mal acostumbrado.
comentarios cerrados

menéame