Fuente verificadaNivel 4
Algoritmo de Shor
El algoritmo de Shor factoriza grandes enteros en tiempo polinomial O((log N)³), amenazando RSA.
Qué significa
Reduce factorizacion a busqueda de periodo mediante QFT.Motiva criptografia post-cuantica.Analogía cotidiana
Como encontrar el ritmo secreto.
Como encontrar la frecuencia de resonancia de una caja fuerte.
Errores comunes
- No rompe instantaneamente toda encripcion.
- Computadoras cuanticas actuales no pueden ejecutarlo.
Puntos clave
- O((log N)³) factorizacion.
- Reduccion a busqueda de periodo por QFT.
- Motiva criptografia post-cuantica.
Comprueba tu comprensión
¿A que problema reduce Shor la factorizacion?
- A.Multiplicacion matricial
- B.Busqueda de periodo
- C.Coloracion de grafos
- D.Ordenamiento
Ver la respuesta
Respuesta: B. Busqueda de periodo
Por qué: Reduccion a busqueda de periodo.
Se apoya en
Fuente primaria: Shor, SIAM J. Comput. 26, 1484 (1997), doi:10.1137/S0097539795293172
Hardware-status sentences ('current quantum computers cannot factor...') are explicitly era-qualified honesty statements protecting against hype; algorithm itself is established mathematics.
Apréndelo con la práctica
Este concepto forma parte de un plan de 46 niveles, con un simulador interactivo y Lumen, un tutor cuyas respuestas se verifican antes de mostrarse. Los niveles 1–5 son gratuitos.