TecTop
Flujo de trabajo del algoritmo de factorización de enteros cuánticos de recursos sublineales (SQIF). El algoritmo adopta un marco híbrido «clásico+cuántico» en el que se utiliza un optimizador cuántico QAOA para optimizar el algoritmo de factorización de Schnorr clásico. Primero, el problema se preprocesa como un problema de vector más cercano (CVP) en una red. Luego, la computadora cuántica funciona como un optimizador para refinar los vectores clásicos calculados por el algoritmo de Babai, y este paso puede encontrar una solución de CVP de mayor calidad (más cercana). Los resultados optimizados retroalimentarán el procedimiento en el algoritmo de Schnorr. Después del procesamiento posterior, finalmente genere los factores p y q. Crédito: arXiv (2022). DOI: 10.48550/arxiv.2212.12372
Un equipo de investigadores afiliados a una serie de instituciones en China ha modificado el algoritmo de Shor de una manera que podría permitir que las computadoras cuánticas menos potentes descifren los criptosistemas actuales. El equipo describe sus modificaciones y describe los resultados de probarlo usando computadoras cuánticas del mundo real en un artículo publicado en el arXiv servidor de preimpresión.
A principios de la década de 1990, los investigadores desarrollaron claves de cifrado para proteger los sistemas informáticos y los datos que implicaban la multiplicación de dos números primos. Averiguar qué dos números se usaron para crear un número grande determinado resultó ser más de lo que los sistemas convencionales podían manejar a medida que los números crecían.
Pero luego, a mediados de los años 90, el matemático Peter Shor ideó un algoritmo que podría usarse para descifrar tales criptosistemas usando una computadora cuántica. Pero dado que las computadoras cuánticas de la época, o incluso las que existen hoy en día, no han progresado hasta el punto de poder ejecutar el algoritmo, la criptografía permanece segura, pero quizás no por mucho tiempo.
En este nuevo esfuerzo, los investigadores han modificado el algoritmo de Shor (llaman al suyo algoritmo de Schnorr) para usarlo en computadoras cuánticas mucho menos poderosas. Su trabajo involucró un algoritmo de optimización para acelerar el procesamiento de los pasos que requieren más trabajo en el algoritmo original y, por lo tanto, la mayor parte del tiempo. Y demostraron que funciona al factorizar un número de 48 bits en una computadora cuántica con solo 10 qubits.
Sugieren que pronto podrán factorizar números mucho más largos, poniendo en riesgo los criptosistemas convencionales. Estiman que una computadora cuántica que use 372 qubits ejecutando su algoritmo podría descifrar cualquiera de los criptosistemas que se usan hoy en día. No se menciona en su trabajo una advertencia que permanece: las computadoras cuánticas de hoy en día tienen tasas de error tan altas que sería imposible usarlas para descifrar criptosistemas.
Si en un futuro cercano surgen sistemas con tasas de error mucho más bajas, los fabricantes de criptosistemas podrían aumentar el tamaño de los números primos utilizados para generar sus claves, pero solo por un tiempo limitado. Una perspectiva más probable para proteger los sistemas informáticos en el futuro utilizará comunicaciones cuánticas seguras, específicamente la distribución de claves cuánticas.
Bao Yan et al, Factorización de enteros con recursos sublineales en un procesador cuántico superconductor, arXiv (2022). DOI: 10.48550/arxiv.2212.12372
© 2023 Ciencia X Red
Citación: La modificación del algoritmo de Shor puede significar que las computadoras cuánticas menos potentes podrían descifrar los criptosistemas (11 de enero de 2023) recuperado el 11 de enero de 2023 de https://techxplore.com/news/2023-01-modification-shor-algorithm-powerful-quantum.html
Este documento está sujeto a derechos de autor. Aparte de cualquier trato justo con fines de estudio o investigación privados, ninguna parte puede reproducirse sin el permiso por escrito. El contenido se proporciona únicamente con fines informativos.
