dorsal/arxiv
View SchemaImproving the Success Probability for Shor's Factoring Algorithm
| Authors | Gregor Leander |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0208183 |
| URL | https://arxiv.org/abs/quant-ph/0208183 |
Abstract
Given n=p*q with p and q prim and y in Z_{p*q}^*. Shor's Algorithm computes the order r of y, i.e. y^r=1 (mod n). If r=2k is even and y^k \ne -1 (mod n) we can easily compute a non trivial factor of n: gcd(y^k-1,n). In the original paper it is shown that a randomly chosen y is usable for factoring with probabily {1/2}. In this paper we will show an efficient possibility to improve the lower bound of this probability by selecting only special y in Z_n^* to {3/4}, so we are able to reduce the fault probabilty in the worst case from {1/2} to {1/4}.
{
"annotation_id": "edd4b9eb-e46e-411d-9ecf-9a6002717301",
"date_created": "2026-03-02T18:01:53.114000Z",
"date_modified": "2026-03-02T18:01:53.114000Z",
"file_hash": "f9bdafcf439d8810293c03ba03e38aa56ab1d8d2a4d10fd7d0486dc64c41453c",
"private": false,
"record": {
"abstract": "Given n=p*q with p and q prim and y in Z_{p*q}^*. Shor\u0027s Algorithm computes\nthe order r of y, i.e. y^r=1 (mod n). If r=2k is even and y^k \\ne -1 (mod n) we\ncan easily compute a non trivial factor of n: gcd(y^k-1,n). In the original\npaper it is shown that a randomly chosen y is usable for factoring with\nprobabily {1/2}. In this paper we will show an efficient possibility to improve\nthe lower bound of this probability by selecting only special y in Z_n^* to\n{3/4}, so we are able to reduce the fault probabilty in the worst case from\n{1/2} to {1/4}.",
"arxiv_id": "quant-ph/0208183",
"authors": [
"Gregor Leander"
],
"categories": [
"quant-ph"
],
"title": "Improving the Success Probability for Shor\u0027s Factoring Algorithm",
"url": "https://arxiv.org/abs/quant-ph/0208183"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "1d72bb23-c9f9-4177-b8c0-587c9cbc22cc",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}