DOI: 10.1137/s0097539795293172. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

10.1137/s0097539795293172

Crossref journal-article

Society for Industrial & Applied Mathematics (SIAM)

SIAM Journal on Computing (351)

Bibliography

Shor, P. W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 26(5), 1484â1509.

Authors 1

Peter W. Shor (first)

References 51 Referenced 5,073

10.1103/PhysRevA.52.3457
10.1103/PhysRevLett.74.4083
10.1103/PhysRevA.54.1034
10.1007/BF01011339
10.1007/BF01342185
10.1103/PhysRevLett.48.1581
10.1147/rd.176.0525
10.1137/0218053
10.1137/S0097539796300933
10.1103/PhysRevLett.76.722
10.1137/S0097539796300921
10.1080/09500349414552351
10.1126/science.270.5242.1633
10.1103/PhysRevA.52.3489
10.2307/2371045
10.1103/PhysRevLett.74.4091
10.1098/rspa.1985.0070
10.1098/rspa.1989.0099
10.1098/rspa.1995.0065
10.1098/rspa.1992.0167
10.1103/PhysRevA.51.1015
10.1103/RevModPhys.68.733
10.1007/BF02650179
10.1007/BF01886518
10.1007/BF01857727
10.1137/0406010
10.1103/PhysRevLett.76.3228
{'volume-title': 'An introduction to the theory of numbers', 'year': '1991', 'author': 'Niven Ivan', 'key': 'R38'} / An introduction to the theory of numbers by Niven Ivan (1991)
{'key': 'R40', 'first-page': '293', 'volume': '145', 'author': 'Karatsuba A.', 'year': '1962', 'journal-title': 'Dokl. Akad. Nauk SSSR', 'ISSN': 'http://id.crossref.org/issn/0002-3264', 'issn-type': 'print'} / Dokl. Akad. Nauk SSSR by Karatsuba A. (1962)
{'key': 'R40', 'first-page': '595', 'volume': '7', 'year': '1963', 'journal-title': 'Sov. Phys. Dokl.', 'ISSN': 'http://id.crossref.org/issn/0038-5689', 'issn-type': 'print'} / Sov. Phys. Dokl. (1963)
10.1098/rsta.1995.0106
{'key': 'R45', 'first-page': '2597', 'volume': '257', 'author': 'Lecerf Yves', 'year': '1963', 'journal-title': 'C. R. Acad. Sci. Paris'} / C. R. Acad. Sci. Paris by Lecerf Yves (1963)
10.1007/BFb0091534
10.1137/0219046
10.1126/science.261.5128.1569
10.1103/PhysRevLett.75.346
10.1111/j.1749-6632.1986.tb12451.x
10.1016/S0022-0000(76)80043-8
10.1098/rspa.1996.0029
10.2307/2269031
10.1145/359340.359342
10.2307/2274761
10.1007/BF02242355
10.1103/PhysRevA.52.R2493
{'key': 'R67', 'first-page': '1340', 'volume': '26', 'author': 'Simon (1994) D.', 'year': '1997', 'journal-title': 'SIAM J. Comput.', 'ISSN': 'http://id.crossref.org/issn/0097-5397', 'issn-type': 'print'} / SIAM J. Comput. by Simon (1994) D. (1997)
10.1103/PhysRevLett.74.4087
10.1103/PhysRevB.37.8111
10.1112/plms/s2-43.6.544
10.1112/plms/s2-43.6.544
10.1103/PhysRevA.51.992
10.1016/0378-4754(86)90105-9

Dates

Type	When
Created	22 years, 2 months ago (June 11, 2003, 11:12 a.m.)
Deposited	8 years, 7 months ago (Jan. 29, 2017, 11:38 a.m.)
Indexed	23 hours, 50 minutes ago (Sept. 4, 2025, 9:17 a.m.)
Issued	27 years, 11 months ago (Oct. 1, 1997)
Published	27 years, 11 months ago (Oct. 1, 1997)
Published Print	27 years, 11 months ago (Oct. 1, 1997)

Funders 0

None

BibTeX

@article{Shor_1997, title={Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer}, volume={26}, ISSN={1095-7111}, url={http://dx.doi.org/10.1137/s0097539795293172}, DOI={10.1137/s0097539795293172}, number={5}, journal={SIAM Journal on Computing}, publisher={Society for Industrial & Applied Mathematics (SIAM)}, author={Shor, Peter W.}, year={1997}, month=oct, pages={1484–1509} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        9,
        4
      ]
    ],
    "date-time": "2025-09-04T13:17:22Z",
    "timestamp": 1756991842193
  },
  "reference-count": 51,
  "publisher": "Society for Industrial & Applied Mathematics (SIAM)",
  "issue": "5",
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        1997,
        10
      ]
    ]
  },
  "DOI": "10.1137/s0097539795293172",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2003,
        6,
        11
      ]
    ],
    "date-time": "2003-06-11T15:12:06Z",
    "timestamp": 1055344326000
  },
  "page": "1484-1509",
  "source": "Crossref",
  "is-referenced-by-count": 5073,
  "title": "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer",
  "prefix": "10.1137",
  "volume": "26",
  "author": [
    {
      "given": "Peter W.",
      "family": "Shor",
      "sequence": "first",
      "affiliation": []
    }
  ],
  "member": "351",
  "reference": [
    {
      "key": "R3",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.52.3457"
    },
    {
      "key": "R4",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.74.4083"
    },
    {
      "key": "R5",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.54.1034"
    },
    {
      "key": "R6",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF01011339"
    },
    {
      "key": "R7",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF01342185"
    },
    {
      "key": "R8",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.48.1581"
    },
    {
      "key": "R9",
      "doi-asserted-by": "publisher",
      "DOI": "10.1147/rd.176.0525"
    },
    {
      "key": "R10",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/0218053"
    },
    {
      "key": "R11",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/S0097539796300933"
    },
    {
      "key": "R12",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.76.722"
    },
    {
      "key": "R13",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/S0097539796300921"
    },
    {
      "key": "R15",
      "doi-asserted-by": "publisher",
      "DOI": "10.1080/09500349414552351"
    },
    {
      "key": "R21",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.270.5242.1633"
    },
    {
      "key": "R22",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.52.3489"
    },
    {
      "key": "R23",
      "doi-asserted-by": "publisher",
      "DOI": "10.2307/2371045"
    },
    {
      "key": "R24",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.74.4091"
    },
    {
      "key": "R27",
      "doi-asserted-by": "publisher",
      "DOI": "10.1098/rspa.1985.0070"
    },
    {
      "key": "R28",
      "doi-asserted-by": "publisher",
      "DOI": "10.1098/rspa.1989.0099"
    },
    {
      "key": "R29",
      "doi-asserted-by": "publisher",
      "DOI": "10.1098/rspa.1995.0065"
    },
    {
      "key": "R30",
      "doi-asserted-by": "publisher",
      "DOI": "10.1098/rspa.1992.0167"
    },
    {
      "key": "R31",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.51.1015"
    },
    {
      "key": "R32",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/RevModPhys.68.733"
    },
    {
      "key": "R33",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF02650179"
    },
    {
      "key": "R34",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF01886518"
    },
    {
      "key": "R35",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF01857727"
    },
    {
      "key": "R36",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/0406010"
    },
    {
      "key": "R37",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.76.3228"
    },
    {
      "volume-title": "An introduction to the theory of numbers",
      "year": "1991",
      "author": "Niven Ivan",
      "key": "R38"
    },
    {
      "key": "R40",
      "first-page": "293",
      "volume": "145",
      "author": "Karatsuba A.",
      "year": "1962",
      "journal-title": "Dokl. Akad. Nauk SSSR",
      "ISSN": "http://id.crossref.org/issn/0002-3264",
      "issn-type": "print"
    },
    {
      "key": "R40",
      "first-page": "595",
      "volume": "7",
      "year": "1963",
      "journal-title": "Sov. Phys. Dokl.",
      "ISSN": "http://id.crossref.org/issn/0038-5689",
      "issn-type": "print"
    },
    {
      "key": "R43",
      "doi-asserted-by": "publisher",
      "DOI": "10.1098/rsta.1995.0106"
    },
    {
      "key": "R45",
      "first-page": "2597",
      "volume": "257",
      "author": "Lecerf Yves",
      "year": "1963",
      "journal-title": "C. R. Acad. Sci. Paris"
    },
    {
      "key": "R46",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BFb0091534"
    },
    {
      "key": "R48",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/0219046"
    },
    {
      "key": "R49",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.261.5128.1569"
    },
    {
      "key": "R51",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.75.346"
    },
    {
      "key": "R52",
      "doi-asserted-by": "publisher",
      "DOI": "10.1111/j.1749-6632.1986.tb12451.x"
    },
    {
      "key": "R54",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/S0022-0000(76)80043-8"
    },
    {
      "key": "R56",
      "doi-asserted-by": "publisher",
      "DOI": "10.1098/rspa.1996.0029"
    },
    {
      "key": "R59",
      "doi-asserted-by": "publisher",
      "DOI": "10.2307/2269031"
    },
    {
      "key": "R60",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/359340.359342"
    },
    {
      "key": "R61",
      "doi-asserted-by": "publisher",
      "DOI": "10.2307/2274761"
    },
    {
      "key": "R64",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF02242355"
    },
    {
      "key": "R66",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.52.R2493"
    },
    {
      "key": "R67",
      "first-page": "1340",
      "volume": "26",
      "author": "Simon (1994) D.",
      "year": "1997",
      "journal-title": "SIAM J. Comput.",
      "ISSN": "http://id.crossref.org/issn/0097-5397",
      "issn-type": "print"
    },
    {
      "key": "R68",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.74.4087"
    },
    {
      "key": "R71",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevB.37.8111"
    },
    {
      "key": "R73",
      "doi-asserted-by": "publisher",
      "DOI": "10.1112/plms/s2-43.6.544"
    },
    {
      "key": "R73",
      "doi-asserted-by": "publisher",
      "DOI": "10.1112/plms/s2-43.6.544"
    },
    {
      "key": "R74",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.51.992"
    },
    {
      "key": "R76",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0378-4754(86)90105-9"
    }
  ],
  "container-title": "SIAM Journal on Computing",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "http://epubs.siam.org/doi/pdf/10.1137/S0097539795293172",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2017,
        1,
        29
      ]
    ],
    "date-time": "2017-01-29T16:38:55Z",
    "timestamp": 1485707935000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "http://epubs.siam.org/doi/10.1137/S0097539795293172"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1997,
        10
      ]
    ]
  },
  "references-count": 51,
  "journal-issue": {
    "issue": "5",
    "published-print": {
      "date-parts": [
        [
          1997,
          10
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1137/S0097539795293172"
  ],
  "URL": "http://dx.doi.org/10.1137/S0097539795293172",
  "relation": {},
  "ISSN": [
    "0097-5397",
    "1095-7111"
  ],
  "subject": [],
  "container-title-short": "SIAM J. Comput.",
  "published": {
    "date-parts": [
      [
        1997,
        10
      ]
    ]
  }
}