{
  "annotation_id": "f6156239-6ec7-473a-80b1-60f6163598c1",
  "date_created": "2026-03-02T18:02:38.190000Z",
  "date_modified": "2026-03-02T18:02:38.190000Z",
  "file_hash": "56f8036a267ded6ec3f1f2046d320fd6848e79ebd241787413943af9be65721b",
  "private": false,
  "record": {
    "abstract": "A digital computer is generally believed to be an efficient universal\ncomputing device; that is, it is believed able to simulate any physical\ncomputing device with an increase in computation time of at most a polynomial\nfactor. This may not be true when quantum mechanics is taken into\nconsideration. This paper considers factoring integers and finding discrete\nlogarithms, two problems which are generally thought to be hard on a classical\ncomputer and have been used as the basis of several proposed cryptosystems.\nEfficient randomized algorithms are given for these two problems on a\nhypothetical quantum computer. These algorithms take a number of steps\npolynomial in the input size, e.g., the number of digits of the integer to be\nfactored.",
    "arxiv_id": "quant-ph/9508027",
    "authors": [
      "Peter W. Shor"
    ],
    "categories": [
      "quant-ph"
    ],
    "doi": "10.1137/S0097539795293172",
    "journal_ref": "SIAM J.Sci.Statist.Comput. 26 (1997) 1484",
    "title": "Polynomial-Time Algorithms for Prime Factorization and Discrete   Logarithms on a Quantum Computer",
    "url": "https://arxiv.org/abs/quant-ph/9508027"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "c41a2060-0f88-4f0c-bf88-8e130798e752",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}