Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1408.2738 · Quantum Information Processing

Odd orders in Shor’s factoring algorithm

Thomas Lawson

Published Jan 9, 2015• 12 citations
arXivHTMLPDF
DOI
10.1007/s11128-014-0910-z

Related papers

Shor's Algorithm and Factoring: Don't Throw Away the Odd Orders.

Anna M. Johnston

•Jan 1, 2017•5 citations

Shor’s Factoring Algorithm

WORLD SCIENTIFIC eBooks•Jul 11, 2022•4 citations

Factoring Safe Semiprimes with a Single Quantum Query

Frédéric Grosshans, Thomas Lawson, François Morain +1 more

Shor's factoring algorithm (SFA), by its ability to efficiently factor large numbers, has the potential to undermine contemporary encryption. At its heart is a process called order finding, which quantum mechanics lets us perform efficiently. SFA thus consists of a \emph{quantum order finding algorithm} (QOFA), bookended by classical routines which, given the order, return the factors. But, with probability up to $1/2$, these classical routines fail, and QOFA must be rerun. We modify these routines using elementary results in number theory, improving the likelihood that they return the factors. The resulting quantum factoring algorithm is better than SFA at factoring safe semiprimes, an important class of numbers used in cryptography. With just one call to QOFA, our algorithm almost always factors safe semiprimes. As well as a speed-up, improving efficiency gives our algorithm other, practical advantages: unlike SFA, it does not need a randomly picked input, making it simpler to construct in the lab; and in the (unlikely) case of failure, the same circuit can be rerun, without modification. We consider generalizing this result to other cases, although we do not find a simple extension, and conclude that SFA is still the best algorithm for general numbers (non safe semiprimes, in other words). Even so, we present some simple number theoretic tricks for improving SFA in this case.

arXiv:1511.04385•Nov 13, 2015•15 citations

Diffusion Computation versus Quantum Computation: A Comparative Model for Order Finding and Factoring

Carlos Alberto Cadavid, Paulina Hoyos, Jay A. Jorgenson +2 more

We study a hybrid computational model for integer factorization in which the only non-classical resource is access to an \emph{iterated diffusion process} on a finite graph. Concretely, a \emph{diffusion step} is defined to be one application of a symmetric stochastic matrix (the half-lazy walk operator) to an $\ell^{1}$--normalized state vector, followed by an optional readout of selected coordinates. Let $N\ge 3$ be an odd integer which is neither prime nor a prime power, and let $b\in(\mathbb{Z}/N\mathbb{Z})^\ast$ have odd multiplicative order $r={\rm ord}_N(b)$. We construct, without knowing $r$ in advance, a weighted Cayley graph whose vertex set is the cyclic subgroup $\langle b\rangle$ and whose edges correspond to the powers $b^{\pm 2^t}$ for $t\le \lfloor \log_2 N\rfloor+1$. Using an explicit spectral decomposition together with an elementary doubling lemma, we show that $r$ can be recovered from a single heat-kernel value after at most $O((\log_2 N)^2)$ diffusion steps, with an effective bound. We then combine this order-finding model with the standard reduction from factoring to order finding (in the spirit of Shor's framework) to obtain a randomized factorization procedure whose success probability depends only on the number $m$ of distinct prime factors of $N$. Our comparison with Shor's algorithm is \emph{conceptual and model-based}. We replace unitary $\ell^2$ evolution by Markovian $\ell^1$ evolution, and we report complexity in two cost measures: digital steps and diffusion steps. Finally, we include illustrative examples and discussion of practical implementations.

arXiv:2601.02518•Jan 5, 2026•0 citations

Shor’s Factoring Algorithm

WORLD SCIENTIFIC eBooks•Mar 10, 2026•0 citations

Shor’s Algorithm for Integer Factorization

Franklin de Lima Marquezino, Renato Portugal, Carlile Lavor

SpringerBriefs in computer science•Jan 1, 2019•16 citations
Shor's factoring algorithm (SFA), by its ability to efficiently factor large numbers, has the potential to undermine contemporary encryption. At its heart is a process called order finding, which quantum mechanics lets us perform efficiently. SFA thus consists of a \emph{quantum order finding algorithm} (QOFA), bookended by classical routines which, given the order, return the factors. But, with probability up to 1/21/21/2, these classical routines fail, and QOFA must be rerun. We modify these routines using elementary results in number theory, improving the likelihood that they return the factors. The resulting quantum factoring algorithm is better than SFA at factoring safe semiprimes, an important class of numbers used in cryptography. With just one call to QOFA, our algorithm almost always factors safe semiprimes. As well as a speed-up, improving efficiency gives our algorithm other, practical advantages: unlike SFA, it does not need a randomly picked input, making it simpler to construct in the lab; and in the (unlikely) case of failure, the same circuit can be rerun, without modification. We consider generalizing this result to other cases, although we do not find a simple extension, and conclude that SFA is still the best algorithm for general numbers (non safe semiprimes, in other words). Even so, we present some simple number theoretic tricks for improving SFA in this case.
We study a hybrid computational model for integer factorization in which the only non-classical resource is access to an \emph{iterated diffusion process} on a finite graph. Concretely, a \emph{diffusion step} is defined to be one application of a symmetric stochastic matrix (the half-lazy walk operator) to an ℓ1\ell^{1}ℓ1--normalized state vector, followed by an optional readout of selected coordinates. Let N≥3N\ge 3N≥3 be an odd integer which is neither prime nor a prime power, and let b∈(Z/NZ)∗b\in(\mathbb{Z}/N\mathbb{Z})^\astb∈(Z/NZ)∗ have odd multiplicative order r=ordN(b)r={\rm ord}_N(b)r=ordN​(b). We construct, without knowing rrr in advance, a weighted Cayley graph whose vertex set is the cyclic subgroup ⟨b⟩\langle b\rangle⟨b⟩ and whose edges correspond to the powers b±2tb^{\pm 2^t}b±2t for t≤⌊log⁡2N⌋+1t\le \lfloor \log_2 N\rfloor+1t≤⌊log2​N⌋+1. Using an explicit spectral decomposition together with an elementary doubling lemma, we show that rrr can be recovered from a single heat-kernel value after at most O((log⁡2N)2)O((\log_2 N)^2)O((log2​N)2) diffusion steps, with an effective bound. We then combine this order-finding model with the standard reduction from factoring to order finding (in the spirit of Shor's framework) to obtain a randomized factorization procedure whose success probability depends only on the number mmm of distinct prime factors of NNN. Our comparison with Shor's algorithm is \emph{conceptual and model-based}. We replace unitary ℓ2\ell^2ℓ2 evolution by Markovian ℓ1\ell^1ℓ1 evolution, and we report complexity in two cost measures: digital steps and diffusion steps. Finally, we include illustrative examples and discussion of practical implementations.