{
  "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": "primality-proving",
  "nombre": "Primality Proving",
  "categoria": "Algebraic and Number Theoretic Algorithms",
  "categoria_id": "algebraic",
  "problema": "Certificar que un numero es primo, no solo probablemente primo.",
  "speedup_declarado": "Polynomial",
  "declarado_por": "Quantum Algorithm Zoo",
  "fuente_url": "https://quantumalgorithmzoo.org/#algebraic",
  "implementaciones": [],
  "referencias": [
    {
      "n": 393,
      "cita": "Qi Cheng Primality Proving via One Round in ECPP and One Iteration in AKS Journal of Cryptology , Volume 20, Issue 3, pg. 375-387, July 2007.",
      "url": null
    },
    {
      "n": 394,
      "cita": "Daniel J. Bernstein Proving primality in essentially quartic random time Mathematics of Computation , Vol. 76, pg. 389-403, 2007.",
      "url": null
    },
    {
      "n": 395,
      "cita": "F. Morain Implementing the asymptotically fast version of the elliptic curve primality proving algorithm Mathematics of Computation , Vol. 76, pg. 493-505, 2007.",
      "url": null
    },
    {
      "n": 396,
      "cita": "Alvaro Donis-Vela and Juan Carlos Garcia-Escartin A quantum primality test with order finding arXiv:1711.02616 , 2017.",
      "url": "https://arxiv.org/abs/1711.02616"
    },
    {
      "n": 397,
      "cita": "H. F. Chau and H.-K. Lo Primality test via quantum factorization International Journal of Modern Physics C , Vol. 8, No. 2, pg. 131-138, 1997. [ arXiv:quant-ph/9508005 ]",
      "url": "https://arxiv.org/abs/quant-ph/9508005"
    },
    {
      "n": 398,
      "cita": "David Harvey and Joris Van Der Hoeven Integer multiplication in time \\( O(n \\log \\ n) \\) hal-02070778 , 2019.",
      "url": "https://hal.archives-ouvertes.fr/hal-02070778"
    },
    {
      "n": 399,
      "cita": "Charles Greathouse personal communication , 2019.",
      "url": null
    }
  ],
  "n_referencias": 7,
  "remisiones": [],
  "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."
  }
}