DOI: 10.1137/s0036144598347011. 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/s0036144598347011

Crossref journal-article

Society for Industrial & Applied Mathematics (SIAM)

SIAM Review (351)

Bibliography

Shor, P. W. (1999). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Review, 41(2), 303â332.

Authors 1

Peter W. Shor (first)

References 74 Referenced 2,228

10.1103/PhysRevLett.79.2586
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.70.1895
10.1103/PhysRevLett.76.722
10.1109/18.720553
10.1137/S0097539796300921
10.1080/09500349414552351
10.1145/164996.165002 / SIGACT News by Brassard G. (1993)
10.1103/PhysRevLett.78.405
10.1109/18.681315
10.1103/PhysRevA.54.1098
10.1126/science.270.5242.1633
10.1103/PhysRevA.52.3489
10.2307/2371045
10.1103/PhysRevLett.74.4091
10.1103/PhysRevA.56.1201
10.1073/pnas.94.5.1634
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.1103/PhysRevLett.77.2585
10.1007/BF02650179
10.1007/BF01886518
10.1007/BF01857727
10.1126/science.275.5298.350
10.1137/0406010
10.1103/PhysRevA.54.1862
10.1103/PhysRevLett.76.3228
10.1103/PhysRevLett.79.325
{'key': 'R55', 'volume-title': 'An introduction to the theory of numbers', 'author': 'Niven Ivan', 'year': '1991'} / An introduction to the theory of numbers by Niven Ivan (1991)
10.1038/30156
{'key': 'R58', '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': 'R58', '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.1103/PhysRevA.55.900
10.1126/science.279.5349.342
10.1098/rsta.1995.0106
{'key': 'R66', 'first-page': '2597', 'volume': '257', 'author': 'Lecerf Y.', 'year': '1963', 'journal-title': 'C. R. Acad. Française Sci.'} / C. R. Acad. Française Sci. by Lecerf Y. (1963)
10.1007/BFb0091534
10.1137/0219046
10.1126/science.261.5128.1569
10.1126/science.263.5147.695
10.1103/PhysRevLett.75.346
10.1126/science.273.5278.1073
10.1111/j.1749-6632.1986.tb12451.x
10.1016/S0022-0000(76)80043-8
10.1098/rspa.1996.0029
10.2307/2269031
10.1016/S0960-0779(98)00218-5
10.1145/359340.359342
10.2307/2274761
10.1007/BF02242355
10.1103/PhysRevA.52.R2493
10.1137/S0097539796298637
10.1103/PhysRevLett.74.4087
10.1103/PhysRevLett.77.793
10.1098/rspa.1996.0136
10.1080/09500340008244053
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
10.1098/rspa.1998.0162

Dates

Type	When
Created	22 years, 2 months ago (June 11, 2003, 11:12 a.m.)
Deposited	8 years, 2 months ago (June 15, 2017, 5:53 p.m.)
Indexed	15 hours, 10 minutes ago (Aug. 22, 2025, 12:45 a.m.)
Issued	26 years, 7 months ago (Jan. 1, 1999)
Published	26 years, 7 months ago (Jan. 1, 1999)
Published Print	26 years, 7 months ago (Jan. 1, 1999)

Funders 0

None

BibTeX

@article{Shor_1999, title={Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer}, volume={41}, ISSN={1095-7200}, url={http://dx.doi.org/10.1137/s0036144598347011}, DOI={10.1137/s0036144598347011}, number={2}, journal={SIAM Review}, publisher={Society for Industrial & Applied Mathematics (SIAM)}, author={Shor, Peter W.}, year={1999}, month=jan, pages={303–332} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        22
      ]
    ],
    "date-time": "2025-08-22T04:45:45Z",
    "timestamp": 1755837945320
  },
  "reference-count": 74,
  "publisher": "Society for Industrial & Applied Mathematics (SIAM)",
  "issue": "2",
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        1999,
        1
      ]
    ]
  },
  "DOI": "10.1137/s0036144598347011",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2003,
        6,
        11
      ]
    ],
    "date-time": "2003-06-11T15:12:06Z",
    "timestamp": 1055344326000
  },
  "page": "303-332",
  "source": "Crossref",
  "is-referenced-by-count": 2228,
  "title": "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer",
  "prefix": "10.1137",
  "volume": "41",
  "author": [
    {
      "given": "Peter W.",
      "family": "Shor",
      "sequence": "first",
      "affiliation": []
    }
  ],
  "member": "351",
  "reference": [
    {
      "key": "R1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.79.2586"
    },
    {
      "key": "R5",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.52.3457"
    },
    {
      "key": "R6",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.74.4083"
    },
    {
      "key": "R7",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.54.1034"
    },
    {
      "key": "R8",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF01011339"
    },
    {
      "key": "R9",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF01342185"
    },
    {
      "key": "R10",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.48.1581"
    },
    {
      "key": "R11",
      "doi-asserted-by": "publisher",
      "DOI": "10.1147/rd.176.0525"
    },
    {
      "key": "R12",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/0218053"
    },
    {
      "key": "R13",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/S0097539796300933"
    },
    {
      "key": "R15",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.70.1895"
    },
    {
      "key": "R16",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.76.722"
    },
    {
      "key": "R17",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/18.720553"
    },
    {
      "key": "R18",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/S0097539796300921"
    },
    {
      "key": "R20",
      "doi-asserted-by": "publisher",
      "DOI": "10.1080/09500349414552351"
    },
    {
      "key": "R24",
      "doi-asserted-by": "crossref",
      "first-page": "16",
      "DOI": "10.1145/164996.165002",
      "volume": "24",
      "author": "Brassard G.",
      "year": "1993",
      "journal-title": "SIGACT News",
      "ISSN": "http://id.crossref.org/issn/0163-5700",
      "issn-type": "print"
    },
    {
      "key": "R26",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.78.405"
    },
    {
      "key": "R27",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/18.681315"
    },
    {
      "key": "R28",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.54.1098"
    },
    {
      "key": "R31",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.270.5242.1633"
    },
    {
      "key": "R32",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.52.3489"
    },
    {
      "key": "R33",
      "doi-asserted-by": "publisher",
      "DOI": "10.2307/2371045"
    },
    {
      "key": "R34",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.74.4091"
    },
    {
      "key": "R36",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.56.1201"
    },
    {
      "key": "R38",
      "doi-asserted-by": "publisher",
      "DOI": "10.1073/pnas.94.5.1634"
    },
    {
      "key": "R39",
      "doi-asserted-by": "publisher",
      "DOI": "10.1098/rspa.1985.0070"
    },
    {
      "key": "R40",
      "doi-asserted-by": "publisher",
      "DOI": "10.1098/rspa.1989.0099"
    },
    {
      "key": "R41",
      "doi-asserted-by": "publisher",
      "DOI": "10.1098/rspa.1995.0065"
    },
    {
      "key": "R42",
      "doi-asserted-by": "publisher",
      "DOI": "10.1098/rspa.1992.0167"
    },
    {
      "key": "R43",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.51.1015"
    },
    {
      "key": "R44",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/RevModPhys.68.733"
    },
    {
      "key": "R45",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.77.2585"
    },
    {
      "key": "R46",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF02650179"
    },
    {
      "key": "R47",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF01886518"
    },
    {
      "key": "R48",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF01857727"
    },
    {
      "key": "R49",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.275.5298.350"
    },
    {
      "key": "R50",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/0406010"
    },
    {
      "key": "R51",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.54.1862"
    },
    {
      "key": "R52",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.76.3228"
    },
    {
      "key": "R53",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.79.325"
    },
    {
      "key": "R55",
      "volume-title": "An introduction to the theory of numbers",
      "author": "Niven Ivan",
      "year": "1991"
    },
    {
      "key": "R57",
      "doi-asserted-by": "publisher",
      "DOI": "10.1038/30156"
    },
    {
      "key": "R58",
      "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": "R58",
      "first-page": "595",
      "volume": "7",
      "year": "1963",
      "journal-title": "Sov. Phys. Dokl.",
      "ISSN": "http://id.crossref.org/issn/0038-5689",
      "issn-type": "print"
    },
    {
      "key": "R61",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.55.900"
    },
    {
      "key": "R62",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.279.5349.342"
    },
    {
      "key": "R64",
      "doi-asserted-by": "publisher",
      "DOI": "10.1098/rsta.1995.0106"
    },
    {
      "key": "R66",
      "first-page": "2597",
      "volume": "257",
      "author": "Lecerf Y.",
      "year": "1963",
      "journal-title": "C. R. Acad. Fran\u00e7aise Sci."
    },
    {
      "key": "R67",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BFb0091534"
    },
    {
      "key": "R69",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/0219046"
    },
    {
      "key": "R70",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.261.5128.1569"
    },
    {
      "key": "R71",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.263.5147.695"
    },
    {
      "key": "R72",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.75.346"
    },
    {
      "key": "R73",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.273.5278.1073"
    },
    {
      "key": "R74",
      "doi-asserted-by": "publisher",
      "DOI": "10.1111/j.1749-6632.1986.tb12451.x"
    },
    {
      "key": "R78",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/S0022-0000(76)80043-8"
    },
    {
      "key": "R80",
      "doi-asserted-by": "publisher",
      "DOI": "10.1098/rspa.1996.0029"
    },
    {
      "key": "R83",
      "doi-asserted-by": "publisher",
      "DOI": "10.2307/2269031"
    },
    {
      "key": "R85",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/S0960-0779(98)00218-5"
    },
    {
      "key": "R86",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/359340.359342"
    },
    {
      "key": "R87",
      "doi-asserted-by": "publisher",
      "DOI": "10.2307/2274761"
    },
    {
      "key": "R90",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF02242355"
    },
    {
      "key": "R92",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.52.R2493"
    },
    {
      "key": "R95",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/S0097539796298637"
    },
    {
      "key": "R96",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.74.4087"
    },
    {
      "key": "R98",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.77.793"
    },
    {
      "key": "R99",
      "doi-asserted-by": "publisher",
      "DOI": "10.1098/rspa.1996.0136"
    },
    {
      "key": "R100",
      "doi-asserted-by": "publisher",
      "DOI": "10.1080/09500340008244053"
    },
    {
      "key": "R102",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevB.37.8111"
    },
    {
      "key": "R104",
      "doi-asserted-by": "publisher",
      "DOI": "10.1112/plms/s2-43.6.544"
    },
    {
      "key": "R104",
      "doi-asserted-by": "publisher",
      "DOI": "10.1112/plms/s2-43.6.544"
    },
    {
      "key": "R105",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.51.992"
    },
    {
      "key": "R107",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0378-4754(86)90105-9"
    },
    {
      "key": "R109",
      "doi-asserted-by": "publisher",
      "DOI": "10.1098/rspa.1998.0162"
    }
  ],
  "container-title": "SIAM Review",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "http://epubs.siam.org/doi/pdf/10.1137/S0036144598347011",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2017,
        6,
        15
      ]
    ],
    "date-time": "2017-06-15T21:53:39Z",
    "timestamp": 1497563619000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "http://epubs.siam.org/doi/10.1137/S0036144598347011"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1999,
        1
      ]
    ]
  },
  "references-count": 74,
  "journal-issue": {
    "issue": "2",
    "published-print": {
      "date-parts": [
        [
          1999,
          1
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1137/S0036144598347011"
  ],
  "URL": "http://dx.doi.org/10.1137/S0036144598347011",
  "relation": {},
  "ISSN": [
    "0036-1445",
    "1095-7200"
  ],
  "subject": [],
  "container-title-short": "SIAM Rev.",
  "published": {
    "date-parts": [
      [
        1999,
        1
      ]
    ]
  }
}