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
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".
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".
El presente trabajo de integración curricular tiene como objetivo analizar y comparar el desempeño de un algoritmo de búsqueda clásico y de un cuántico, en específico el algoritmo de Grover, con el fin de analizar y contrastar la ventaja computacional teórica y asintótica que proporciona la computación cuántica frente a los algoritmos clásicos, considerando las limitaciones del hardware cuántico actual. Se analizan las bases teóricas de estos dos enfoques, su complejidad temporal y su comportamiento frente a conjuntos de datos de tamaño distinto. La metodología que se emplea es la simulación de ambos algoritmos, es experimental, ya que permite observar y realizar comparaciones de tiempo y eficiencia para la localización de un elemento objetivo. En el caso del algoritmo cuántico, se implementa el algoritmo de Grover mediante simuladores cuánticos, analizando el impacto del número de qubits y de las iteraciones en los resultados obtenidos. Los resultados muestran que para la búsqueda clásica la complejidad de tiempo es O(n) en cambio en el caso del algoritmo de Grover esta se reduce a O(√n) siendo una mejora interesante que se centra en un n grande. A pesar de esto, existen limitaciones en la implementación de ordenadores cuánticos en la actualidad. Por último, se concluyó que el algoritmo de Grover es una alternativa bastante interesante para resolver problemas de búsqueda no estructurada y se muestra el potencial de la computación cuántica como una tecnología emergente con aplicaciones en la ingeniería.
Este proyecto de titulación se centra en la aplicación de la computación cuántica a través del entorno Qiskit, con el objetivo de analizar la seguridad criptográfica en relación con la comparación entre cifrados clásicos y cuánticos. El análisis se desarrolla mediante el estudio del espacio de búsqueda de claves en esquemas criptográficos simétricos, considerando escenarios de tamaño reducido que permiten evaluar su comportamiento bajo modelos de cómputo clásico y cuántico. Para el enfoque cuántico, se emplea el algoritmo de Grover, el cual es implementado en un simulador cuántico mediante la construcción de circuitos que incluyen la inicialización en superposición uniforme, el oráculo de fase para marcar el estado objetivo y el operador de difusión encargado de la amplificación de amplitudes. Las simulaciones se ejecutan para diferentes cantidades de iteraciones, lo que permite analizar la evolución de la probabilidad de éxito en función del tamaño del espacio de búsqueda y del número de repeticiones del algoritmo. Las ejecuciones se realizan utilizando una semilla fija, lo que garantiza la reproducibilidad de los resultados y facilita la comparación entre los valores teóricos y los obtenidos mediante simulación. Se registran las probabilidades asociadas al estado marcado, así como el crecimiento del tamaño del circuito cuántico conforme aumenta el número de iteraciones. Los escenarios analizados corresponden a registros de tres y cuatro qubits, lo que permite un análisis detallado del comportamiento del algoritmo. Finalmente, se incorpora la comparación con la búsqueda clásica en los mismos espacios de búsqueda, permitiendo establecer una referencia directa entre ambos enfoques y evidenciar la ventaja del algoritmo de Grover en términos de eficiencia.
La aparición de la computación cuántica plantea una amenaza directa sobre los sistemas criptográficos actualmente desplegados, poniendo en riesgo la confidencialidad y autenticidad de la información. En tal contexto, la criptografía postcuántica surge como una alternativa diseñada para resistir ataques basados en ordenadores cuánticos, empleando como base problemas matemáticos considerados intratables incluso para este escenario. El objetivo de este trabajo es evaluar la viabilidad práctica de los algoritmos criptográficos de tipo postcuántico propuestos por el proceso de estandarización del NIST, comparándolos con algoritmos clásicos muy conocidos. Con tal fin, se ha llevado a cabo un análisis teórico del estado del arte y un estudio experimental basado en microbenchmarks criptográficos y pruebas sobre el protocolo TLS 1.3, usando implementaciones reales y plataformas hardware heterogéneas. La metodología empleada permite estudiar métricas relevantes como tiempos de ejecución, latencias o escalabilidad, tanto en operaciones atómicas como en escenarios de comunicación más amplios. Los resultados muestran que los algoritmos basados en retículos, como ML-KEM y ML-DSA, ofrecen un rendimiento competitivo frente a algoritmos clásicos con nivel de seguridad equivalente, de manera especial en hardware moderno. No obstante se observa un impacto significativo en dispositivos con recursos limitados y en el proceso de handshake TLS. Se concluye que este trabajo demuestra que la criptografía postcuántica es técnicamente viable en numerosos entornos reales, aunque su adopción debe abordarse de forma progresiva y contextualizada, considerando las limitaciones físicas y requisitos de cada sistema.
[ES] La computación cuántica supone un cambio de paradigma con un impacto potencial significativo en el ámbito de la criptografía, especialmente debido a la existencia de algoritmos capaces de resolver problemas considerados intratables en computación clásica. En este trabajo se presenta una implementación del algoritmo de Shor en un entorno de computación clásica, haciendo uso de paralelismo mediante OpenMP, con el objetivo de analizar su comportamiento experimental. Los resultados obtenidos se comparan con los de algoritmos clásicos de factorización, como el método de Fermat y los algoritmos de Pollard. El estudio muestra que la paralelización permite reducir el tiempo de ejecución del algoritmo de Shor, aunque el crecimiento exponencial del espacio de búsqueda impone límites claros a su viabilidad práctica. En conjunto, los resultados ponen de manifiesto tanto el impacto positivo del paralelismo clásico como sus limitaciones fundamentales, reforzando la necesidad de un modelo de computación cuántico para explotar plenamente el potencial teórico del algoritmo de Shor.
El objetivo de esta investigación es proponer una implementación del algoritmo de Grover, un método cuántico que permite reducir significativamente el tiempo de búsqueda en bases de datos no estructuradas. Se aplicó una metodología que integró diferentes experimentos en simuladores y una computadora cuántica en el cual se incluyó el análisis del algoritmo cuántico, y se compara con los algoritmos clásicos deterministas en diferentes escenarios de búsquedas. Se estructura la arquitectura del algoritmo ajustando los parámetros que lo constituyen y tipo de búsqueda. Por ende, dando una versión de los fundamentos de la computación cuántica, destacando los principios de superposición y entrelazamiento como elementos clave para abordar problemas de búsquedas en listas no ordenadas con tecnologías cuánticas. Asimismo, se introducen los conceptos de qubits, compuertas cuánticas, circuitos cuánticos, y se describe la interpretación geométrica de su acción sobre los estados cuánticos mediante la esfera de Bloch. Se detalla el funcionamiento del algoritmo de Grover con la utilización de simuladores cuánticos y su escalabilidad en la computadora cuántica ibmbrisbane, para la estructuración de la solución a problemas de búsqueda en listas no ordenadas, explicando cómo logra una aceleración cuadrática al reducir la complejidad de búsqueda de ( O(N) ) a ( O(sqrt{N}) ). Esta investigación siguió un enfoque cuantitativo, experimental y comparativo, visualizando como este algoritmo representa una ventaja computacional significativa en la resolución de problemas de búsqueda en estructuras de datos no organizadas y con el objeto experimental del tamaño de la búsqueda.
El objetivo principal del presente trabajo es analizar el impacto inminente del desarrollo de la computación cuántica sobre los modelos criptográficos asimétricos tradicionales, como RSA y ECC, sustentados en problemas matemáticos vulnerables a algoritmos cuánticos como Shor y Grover. Con este propósito, se propone, formula, desarrolla e implementa experimentalmente un nuevo modelo criptográfico asimétrico basado en principios de complejidad computacional cuántica, soportado en estructuras reticulares, no linealidad y perturbaciones controladas. El estudio adopta un enfoque interdisciplinario, experimental y cuantitativo, combinando Design Science Research Methodology (DSRM), Scrum, revisión sistemática de literatura (Kitchenham) y análisis estadístico avanzado. Implementado en un entorno reproducible en Python, y se evalúa mediante pruebas de benchmarking sobre tiempos de KeyGen, Encrypt y Decrypt con distintas dimensiones de retícula. Los resultados se analizan mediante ANOVA de un factor y modelos lineales, demostrando diferencias significativas entre dimensiones y una correlación lineal directa entre el tamaño del problema y el tiempo de ejecución, reflejada en altos valores de F, niveles de significación p extremadamente bajos y coeficientes de determinación elevados (R2 > 0,93). Además, el modelo se compara con RSA y ECC mediante la matriz de Holmes y se valida bajo el estándar ISO/IEC 25010 en funcionalidad, eficiencia y seguridad. Los resultados evidencian que el modelo propuesto es eficiente, estructuralmente seguro y con capacidad de reemplazar esquemas criptográficos clásicos en infraestructuras digitales críticas en un futuro cercano.