Estudio comparativo de soluciones algorítmicas bajo el contexto de la Computación Clásica y Computación Cuántica : Estudio comparativo de soluciones algorítmicas bajo el contexto de la Computación Clásica y Computación Cuántica para la Factorización de números enteros grandes
Jorge Ricardo Teran Sosa
Abstract
El presente trabajo desarrolla un estudio comparativo entre algoritmos de factorización de números enteros bajo los paradigmas de computación clásica y cuántica, en el contexto de sus implicaciones para la criptografía moderna. La factorización de enteros grandes constituye la base de seguridad del sistema criptográfico RSA, ampliamente utilizado en comunicaciones digitales seguras. Mientras los algoritmos clásicos presentan complejidad sub-exponencial, el algoritmo de Shor ofrece una solución en tiempo polinómico O((logN)3)O((\log N)^3) O((logN)3), representando una amenaza potencial para los esquemas criptográficos vigentes. Como solución clásica se implementó el algoritmo Quadratic Sieve, y como solución cuántica se implementó el algoritmo de Shor utilizando el framework Qiskit de IBM. Las pruebas se ejecutaron en tres entornos: Python para el algoritmo clásico, el simulador Qiskit Aer, y el procesador cuántico real IBM Torino de 133 qubits. Se evaluaron métricas de tiempo de ejecución, tasa de éxito y recursos computacionales sobre un conjunto de 16 semiprimos en el rango N∈[15,1147]N \in [15, 1147] N∈[15,1147]. La metodología cuántica empleó circuitos compilados basados en el Teorema Chino del Resto, seleccionando estratégicamente el parámetro aa a para garantizar un período r=2r=2 r=2, lo que permitió reducir la profundidad del circuito de más de 82,000 compuertas a tan solo 47–52 compuertas. Esta optimización fue clave para operar dentro de los tiempos de coherencia del hardware NISQ actual. Los resultados muestran que el algoritmo clásico supera al cuántico simulado por un factor de 10410^4 104 en los valores evaluados, debido al overhead inherente de simular sistemas cuánticos en hardware clásico. Sin embargo, la ejecución en hardware real alcanzó una tasa de éxito del 100% en la factorización de los 16 semiprimos, gracias a la reducción de profundidad del circuito. El análisis teórico de complejidad confirma que la ventaja de Shor se manifiesta para N>2512N > 2^{512} N>2512, punto en el que las curvas de complejidad divergen más de 20 órdenes de magnitud. Se concluye que, aunque las limitaciones actuales del hardware cuántico NISQ impiden explotar la ventaja teórica de Shor a escala criptográfica, los resultados experimentales validan la viabilidad del algoritmo en hardware real y justifican la transición proactiva hacia esquemas de criptografía post-cuántica ante la amenaza del paradigma "harvest now, decrypt later".