El algoritmo de Shor

Abstract

[es] En este trabajo, se analiza el desarrollo y la relevancia del algoritmo de Shor de factorización de enteros $N=pq$. Se destaca su potencial impacto en la criptografía clásica, particularmente como una amenaza emergente al criptosistema de clave pública RSA. Para una comprensión completa del algoritmo y su importancia desde una perspectiva matemática, se introducen los fundamentos de mecánica cuántica y teorı́a de números sobre los cuales se fundamenta. El estudio profundiza en el algoritmo, destacando su complejidad mejorada de $O((log N)^{3})$ en comparación con la mejor alternativa clásica conocida, cuya complejidad es de $O(e^{(log N)^{1/3}})$. [en] This paper examines the development and relevance of Shor’s algorithm for factoring integers $N=pq$. Its potential impact on classical cryptography is highlighted, particularly as an emerging threat to the RSA public-key cryptosystem. To fully grasp the algorithm and its mathematical significance, we introduce the fundamentals of quantum mechanics and number theory upon which it is based. The study explores the algorithm in depth, highlighting its improved complexity of $O((log N)^{3})$ compared to the best-known classical alternative, which has a complexity of $O(e^{(log N)^{1/3}})$.