dorsal/arxiv
View SchemaShor's Factoring Algorithm and Modern Cryptography. An Illustration of the Capabilities Inherent in Quantum Computers
| Authors | Edward Gerjuoy |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0411184 |
| URL | https://arxiv.org/abs/quant-ph/0411184 |
| DOI | 10.1119/1.1891170 |
Abstract
The security of messages encoded via the widely used RSA public key encryption system rests on the enormous computational effort required to find the prime factors of a large number N using classical (i.e., conventional) computers. In 1994, however, Peter Shor showed that for sufficiently large N a quantum computer would be expected to perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the non-expert readers of this journal: (i) the RSA encryption protocol; (ii) the various quantum computer manipulations constituting the Shor algorithm; (iii) how the Shor algorithm performs the factoring; and (iv) the precise sense in which a quantum computer employing Shor's algorithm can be said to accomplish the factoring of very large numbers with less computational effort than a classical computer can. It is made apparent that factoring $N$ generally requires many successive runs of the algorithm. The careful analysis herein reveals, however, that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.
{
"annotation_id": "2d9a20ff-9e5b-46e0-b1a8-24c9bbf33fab",
"date_created": "2026-03-02T18:02:13.741000Z",
"date_modified": "2026-03-02T18:02:13.741000Z",
"file_hash": "6adf1d657c7e21571a6e73bfff2bbebb76ee313e1d01523c615f8aaf0d399cf3",
"private": false,
"record": {
"abstract": "The security of messages encoded via the widely used RSA public key\nencryption system rests on the enormous computational effort required to find\nthe prime factors of a large number N using classical (i.e., conventional)\ncomputers. In 1994, however, Peter Shor showed that for sufficiently large N a\nquantum computer would be expected to perform the factoring with much less\ncomputational effort. This paper endeavors to explain, in a fashion\ncomprehensible to the non-expert readers of this journal: (i) the RSA\nencryption protocol; (ii) the various quantum computer manipulations\nconstituting the Shor algorithm; (iii) how the Shor algorithm performs the\nfactoring; and (iv) the precise sense in which a quantum computer employing\nShor\u0027s algorithm can be said to accomplish the factoring of very large numbers\nwith less computational effort than a classical computer can. It is made\napparent that factoring $N$ generally requires many successive runs of the\nalgorithm. The careful analysis herein reveals, however, that the probability\nof achieving a successful factorization on a single run is about twice as large\nas commonly quoted in the literature.",
"arxiv_id": "quant-ph/0411184",
"authors": [
"Edward Gerjuoy"
],
"categories": [
"quant-ph"
],
"doi": "10.1119/1.1891170",
"title": "Shor\u0027s Factoring Algorithm and Modern Cryptography. An Illustration of the Capabilities Inherent in Quantum Computers",
"url": "https://arxiv.org/abs/quant-ph/0411184"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "8e8561fe-e737-4296-88d2-b5a2f89017bd",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}