{
  "aviso": "speedup_declarado es lo que declara la fuente citada, NO una medición de Rosetta. Lo que Rosetta midió va en evidencia_rosetta, y para la mayoría del catálogo está vacío.",
  "procedencia": {
    "fuente": "Quantum Algorithm Zoo",
    "fuente_url": "https://quantumalgorithmzoo.org/",
    "instantanea_sha256": "dee7e76b5f19096ed329c88714744b93babf7b7d0296eb97e357b2582d16b75e",
    "generado_at": "2026-08-09"
  },
  "id": "factoring",
  "nombre": "Factoring",
  "categoria": "Algebraic and Number Theoretic Algorithms",
  "categoria_id": "algebraic",
  "problema": "Descomponer un entero de n bits en sus factores primos. Es el problema sobre el que descansa RSA.",
  "speedup_declarado": "Superpolynomial",
  "declarado_por": "Quantum Algorithm Zoo",
  "fuente_url": "https://quantumalgorithmzoo.org/#algebraic",
  "implementaciones": [
    {
      "nombre": "Classiq",
      "url": "https://short.classiq.io/shor"
    },
    {
      "nombre": "Cirq",
      "url": "https://github.com/quantumlib/Cirq/blob/main/examples/shor.py"
    },
    {
      "nombre": "PennyLane",
      "url": "https://pennylane.ai/codebook/shors-algorithm"
    },
    {
      "nombre": "Qrisp",
      "url": "https://qrisp.eu/reference/Algorithms/Shor.html#shor"
    }
  ],
  "referencias": [
    {
      "n": 82,
      "cita": "Peter W. Shor Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing , 26(5):1484-1509, 1997. [ arXiv:quant-ph/9508027 ]",
      "url": "http://arxiv.org/abs/quant-ph/9508027"
    },
    {
      "n": 125,
      "cita": "Peter Shor Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In Proceedings of FOCS 1994 , pg. 124-134.",
      "url": null
    },
    {
      "n": 248,
      "cita": "Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, Eds. Post-Quantum Cryptography Springer , 2009.",
      "url": "http://www.springer.com/mathematics/numbers/book/978-3-540-88701-0"
    },
    {
      "n": 252,
      "cita": "J. M. Pollard Theorems on factorization and primality testing Proceedings of the Cambridge Philosophical Society. 76:521-228, 1974.",
      "url": null
    },
    {
      "n": 253,
      "cita": "L. Babai, R. Beals, and A. Seress Polynomial-time theory of matrix groups In Proceedings of STOC 2009 , pg. 55-64.",
      "url": null
    },
    {
      "n": 254,
      "cita": "Neil J. Ross and Peter Selinger Optimal ancilla-free Clifford+T approximations of z-rotations arXiv:1403.2975 , 2014.",
      "url": "http://arxiv.org/abs/1403.2975"
    },
    {
      "n": 271,
      "cita": "Frédéric Grosshans, Thomas Lawson, François Morain, and Benjamin Smith Factoring safe semiprimes with a single quantum query arXiv:1511.04385 , 2015.",
      "url": "http://arxiv.org/abs/1511.04385"
    },
    {
      "n": 362,
      "cita": "Volker Strassen Einige Resultate über Berechnungskomplexität In Jahresbericht der Deutschen Mathematiker-Vereinigung , 78(1):1-8, 1976/1977.",
      "url": null
    },
    {
      "n": 366,
      "cita": "D. J. Bernstein, N. Heninger, P. Lou, and L. Valenta Post-quantum RSA IACR e-print 2017/351 , 2017.",
      "url": "https://eprint.iacr.org/2017/351"
    },
    {
      "n": 384,
      "cita": "M. Ekerå and J. Håstad Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers Proceedings of PQCrypto 2017 , pg. 347-363. (LNCS Volume 10346), 2017.",
      "url": "https://link.springer.com/chapter/10.1007/978-3-319-59879-6_20"
    },
    {
      "n": 386,
      "cita": "D. J. Bernstein, J.-F. Biasse, and M. Mosca A low-resource quantum factoring algorithm Proceedings of PQCrypto 2017 , pg. 330-346 (LNCS Volume 10346), 2017.",
      "url": "https://link.springer.com/chapter/10.1007/978-3-319-59879-6_19"
    },
    {
      "n": 431,
      "cita": "Craig Gidney and Martin Ekera How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits Quantum 5:433, 2021. [ arXiv:1905.09749 ]",
      "url": "https://arxiv.org/abs/1905.09749"
    },
    {
      "n": 542,
      "cita": "David Harvey and Markus Hittmeir A log-log speedup for exponent one-fifth deterministic integer factorization arXiv:2105.11105 , 2021.",
      "url": "https://arxiv.org/abs/2105.11105"
    }
  ],
  "n_referencias": 13,
  "remisiones": [
    {
      "ancla": "abelian_HSP",
      "url": "https://quantumalgorithmzoo.org/#abelian_HSP"
    }
  ],
  "evidencia_rosetta": {
    "medido": false,
    "lectura": "Rosetta no tiene ninguna corrida sellada sobre este algoritmo. Que esté catalogado no significa que lo hayamos medido ni que lo ofrezcamos."
  }
}