Shor Algorithm

Short Definition

Shor’s algorithm is a family of randomized quantum algorithms that solves integer factoring and discrete logarithms in time polynomial in the input length. Its quantum core does not search through candidate factors. It finds a period, or more generally a hidden subgroup, by preparing a coherent periodic function and decoding its frequency information with a Quantum Fourier Transform; the dedicated page owns the transform circuit and approximation contract, while this page owns period finding and verified arithmetic recovery.

For factoring, the logical chain is

$$\begin{gathered} \text{factoring} \\ \downarrow \\ \text{multiplicative order finding} \\ \downarrow \\ \text{phase estimation and a QFT} \end{gathered}$$

Most of the surrounding work is classical: choose a base, compute greatest common divisors, use continued fractions, verify a candidate order, and retry when a random choice is unhelpful. The quantum work is dominated by reversible modular arithmetic, not by the Fourier transform alone.

This page is the canonical home for the complete reduction, its success conditions, the discrete-logarithm variant, asymptotic complexity, cryptographic consequences, and implementation caveats. Quantum Phase Estimation owns the general eigenphase algorithm and its precision analysis.

What the Algorithm Actually Establishes

Let $N$ be the integer to factor and let

$$n=\left\lceil\log_2N\right\rceil$$

be its bit length. Shor’s result gives a uniform family of quantum circuits, together with polynomial-time classical processing, whose expected runtime is polynomial in $n$. The algorithm is probabilistic, but unsuccessful runs are detectable and repetition raises the success probability.

Several qualifications matter:

• The theorem is about an ideal fault-tolerant computation with scalable coherent arithmetic.
• The algorithm is polynomial in the number of input bits, not in the numerical value $N$.
• Factoring is not known to be NP-complete, and Shor’s result does not make generic NP problems easy.
• The speedup is relative to the best known classical factoring algorithms; no theorem proves that every classical algorithm must be slow.
• The same framework solves discrete logarithms in finite cyclic groups, including the groups used by finite-field and elliptic-curve cryptography.

Calling the result “exponential speedup” is common but imprecise for factoring. The best known general classical algorithm is subexponential rather than fully exponential in $n$, whereas Shor’s algorithm is polynomial. “Superpolynomial improvement over the best known classical method” states the comparison more accurately.

From Factoring to Order Finding

Assume classical preprocessing has removed easy cases: $N$ is odd, composite, and not a prime power. Primality testing, perfect-power detection, modular exponentiation, and greatest common divisors all have polynomial-time classical algorithms.

Choose an integer $a$ uniformly from

$$2\leq a\leq N-1$$

and compute

$$d=\gcd(a,N).$$

If $d>1$, then $d$ is already a nontrivial factor. Otherwise $a$ is invertible modulo $N$, and its multiplicative order modulo $N$ is

$$\begin{aligned} r &= \operatorname{ord}_N(a) \\ &= \min\left\{ r\geq1: a^r\equiv1\pmod N \right\}. \end{aligned}$$

Suppose order finding returns an even $r$. Set

$$x=a^{r/2}\bmod N.$$

Then

$$x^2 \equiv a^r \equiv1 \pmod N,$$

so

$$(x-1)(x+1) \equiv0 \pmod N.$$

Minimality of $r$ implies $x\not\equiv1\pmod N$. If also

$$x\not\equiv-1\pmod N,$$

then neither factor $x-1$ nor $x+1$ is divisible by all of $N$. The classical computations

$$\gcd(x-1,N), \qquad \gcd(x+1,N)$$

therefore reveal nontrivial factors.

If $r$ is odd or $x\equiv-1\pmod N$, the run has supplied no factor. This is not an undetected error: discard that base and try another.

Only order finding is quantum. Every branch is checked classically: a lucky gcd gives a factor immediately, while an odd order or the square root $a^{r/2}\equiv-1\pmod N$ triggers a retry.

Why a useful base occurs often enough

Write the preprocessed odd integer as a product involving $k\geq2$ distinct odd primes. Let $G$ be the event

$$\begin{gathered} r\text{ is even}, \\ a^{r/2}\not\equiv-1\pmod N. \end{gathered}$$

Among bases coprime to $N$, standard finite-group counting shows that

$$\Pr(G) \geq 1-\frac1{2^{k-1}} \geq \frac12.$$

A non-coprime base only helps, because the initial gcd then exposes a factor. Thus exact order finding combined with a random base has a constant probability of making progress. Recovering the full order from one Fourier sample has an additional number-theoretic success factor, discussed below, but polynomially many repetitions suffice.

Worked example: factoring 15

Take $N=15$ and choose $a=2$. Since

$$\gcd(2,15)=1,$$

find the powers

$$\begin{aligned} 2^1&\equiv2, & 2^2&\equiv4, \\ 2^3&\equiv8, & 2^4&\equiv1\pmod{15}. \end{aligned}$$

The order is $r=4$. Therefore

$$x=2^{r/2}=2^2=4$$

and

$$\begin{aligned} \gcd(4-1,15)&=3, \\ \gcd(4+1,15)&=5. \end{aligned}$$

The example illustrates the reduction, but it is too small to demonstrate scalability. A circuit specialized using advance knowledge that the answer is $3\times5$, or that the period is $4$, does not constitute a general implementation of Shor’s algorithm.

Quantum Order Finding

The function

$$f(x)=a^x\bmod N$$

is periodic with least positive period $r$ because

$$f(x+r) = a^xa^r \equiv a^x = f(x) \pmod N.$$

The quantum circuit makes many values of $x$ interfere coherently so that this period appears as a reciprocal spacing in Fourier space.

Periodic-state formulation

Choose a power of two

$$Q=2^t$$

and prepare two registers as

$$\frac1{\sqrt Q} \sum_{x=0}^{Q-1} \lvert x\rangle\lvert1\rangle.$$

Reversible modular exponentiation computes

$$\frac1{\sqrt Q} \sum_{x=0}^{Q-1} \lvert x\rangle \lvert a^x\bmod N\rangle.$$

If the second register is measured with result $a^{x_0}\bmod N$, the first register is left in an approximately periodic progression,

$$\frac1{\sqrt L} \sum_j \lvert x_0+jr\rangle,$$

where only values inside $0\leq x_0+jr<Q$ occur. Measuring the second register is optional: ignoring it produces the same first-register statistics.

Applying the QFT over $\mathbb Z_Q$ gives constructive interference near

$$y \approx \frac{sQ}{r}, \qquad s\in\{0,1,\ldots,r-1\}.$$

The measured ratio $y/Q$ therefore approximates $s/r$. When $r$ divides $Q$, these are exact Fourier bins. In general the peaks have finite width, and continued fractions recover the nearby rational.

Phase-estimation formulation

The same computation can be expressed as eigenphase estimation. On the orbit generated by $a$, define modular multiplication

$$M_a\lvert y\rangle = \lvert ay\bmod N\rangle.$$

Because $\gcd(a,N)=1$, multiplication by $a$ permutes the invertible residues and can be completed to a unitary. The orbit

$$\lvert1\rangle, \lvert a\rangle, \ldots, \lvert a^{r-1}\bmod N\rangle$$

has length $r$. Its Fourier eigenstates are

$$\lvert u_s\rangle = \frac1{\sqrt r} \sum_{k=0}^{r-1} e^{-2\pi isk/r} \lvert a^k\bmod N\rangle,$$

and direct index shifting gives

$$M_a\lvert u_s\rangle = e^{2\pi is/r} \lvert u_s\rangle.$$

The easy input $\lvert1\rangle$ is an equal superposition of these eigenstates:

$$\lvert1\rangle = \frac1{\sqrt r} \sum_{s=0}^{r-1} \lvert u_s\rangle.$$

Consequently QPE applied to $M_a$ samples an eigenphase $s/r$ approximately uniformly over $s$. It is unnecessary to prepare a particular unknown eigenstate.

Controlled powers are efficient arithmetic

QPE calls controlled powers

$$M_a,\, M_a^2,\, M_a^4,\, \ldots,\, M_a^{2^{t-1}}.$$

The crucial identity is

$$M_a^{2^j}\lvert y\rangle = \left\lvert a^{2^j}y\bmod N \right\rangle.$$

Each constant $a^{2^j}\bmod N$ is computed efficiently by classical repeated squaring. The quantum circuit then performs controlled reversible multiplication by that known constant. It does not repeat a base circuit $2^j$ times. This arithmetic structure is what keeps order finding polynomial.

Recovering the Order

Let $y$ be the measured Fourier outcome. Take

$$t=2n, \qquad Q=2^t.$$

Since $Q\geq N^2$ and $r<N$, a nearest-bin outcome obeys

$$\left\lvert \frac yQ-\frac sr \right\rvert \leq \frac1{2Q} < \frac1{2r^2}.$$

Legendre’s continued-fraction theorem says that if $s/r$ is in lowest terms and a rational approximation satisfies this bound, then $s/r$ appears among the continued-fraction convergents of $y/Q$. The candidate denominator is tested by modular exponentiation:

$$a^{r_{\mathrm{cand}}} \stackrel{?}{\equiv} 1 \pmod N.$$

Verification is essential. Finite-resolution outcomes, a non-nearest Fourier bin, or a convergent unrelated to the true phase can all produce a wrong denominator.

When the sampled fraction is not reduced

If

$$g=\gcd(s,r)>1,$$

then

$$\frac sr = \frac{s/g}{r/g}$$

and continued fractions reveal only the divisor $r/g$. The probability that one uniformly sampled $s$ is coprime to $r$ is

$$\frac{\varphi(r)}r,$$

where $\varphi$ is Euler’s totient function. This ratio is not bounded below by a positive constant for all $r$, but it decreases slowly enough that repeated samples remain polynomially sufficient. Practical postprocessing can also combine compatible denominator information, for example by least common multiples, and verify the result.

The end-to-end success probability therefore combines three events:

1. the random base has a useful even order;
2. Fourier sampling lands close enough to a rational $s/r$;
3. the sampled numerator exposes enough of the denominator.

All three failures are detectable. A complete complexity statement counts the repetitions needed to obtain and verify a useful order.

Discrete Logarithms as Hidden Subgroups

Simon’s Algorithm owns hidden-subgroup recovery for $\{0,s\}\le(\mathbb Z_2)^n$ through Hadamard samples and binary equations. This section instead owns the number-theoretic subgroup and recovery problem over $\mathbb Z_r^2$.

Let $G=\langle g\rangle$ be a cyclic group of known order $r$, and suppose

$$h=g^x.$$

The discrete-logarithm problem asks for $x\bmod r$. Define

$$F(a,b) = g^a h^{-b} = g^{a-bx}, \qquad (a,b)\in\mathbb Z_r^2.$$

Two pairs have the same function value exactly when their difference lies in the subgroup

$$H = \left\{ (tx,t): t\in\mathbb Z_r \right\} = \langle(x,1)\rangle.$$

Thus $F$ hides a one-dimensional subgroup of the two-dimensional Abelian group $\mathbb Z_r^2$. A coherent evaluation of $F$, followed by a two-register QFT, samples characters orthogonal to $H$. An observed pair $(u,v)$ satisfies

$$ux+v \equiv0 \pmod r.$$

When $u$ is invertible modulo $r$,

$$x \equiv -vu^{-1} \pmod r.$$

Otherwise several samples supply a solvable modular linear system. Sign conventions vary with the choice of $h^b$ versus $h^{-b}$ and with the Fourier-transform sign; the hidden subgroup, not a memorized sign, is the invariant content.

This construction applies to multiplicative groups of finite fields and, in additive notation, to elliptic-curve groups. For points $P$ and $Q=xP$, the coherent group operation evaluates $aP-bQ$. Efficient reversible point addition replaces modular multiplication, but the Fourier and classical linear-algebra logic is the same.

Complexity and the Source of the Speedup

For an $n$-bit modulus, the order-finding registers contain $O(n)$ qubits and require phase precision $O(1/N^2)$, hence $t=O(n)$ control bits. Standard decompositions give:

• $O(n^2)$ gates for an exact QFT on $O(n)$ qubits;
• polynomial-size reversible circuits for addition and modular multiplication;
• about cubic elementary-gate scaling in common schoolbook-arithmetic constructions;
• polynomially many repetitions for Fourier and number-theoretic success.

The precise exponents and constants depend on the multiplication algorithm, ancilla budget, connectivity, gate alphabet, allowed measurements, and whether cost means gate count, depth, space, or spacetime volume. For example, Beauregard’s compact general construction uses $2n+3$ qubits, $O(n^3\log n)$ elementary gates, and depth $O(n^3)$. It is a logical circuit result, not a physical-qubit estimate. Quantum Complexity Classes defines BQP and explains why membership does not itself prove a classical lower bound.

The Quantum Algorithms and Complexity chapter guide supplies the wider problem, access, output, resource, comparator, and evidence audit: Shor’s polynomial quantum upper bound is not by itself a proved classical superpolynomial lower bound.

By comparison, the general number field sieve has heuristic asymptotic running time

$$\begin{aligned} L_N[1/3,c] &= \exp(\Xi_N), \\ \Xi_N &= (c+o(1)) (\ln N)^{1/3} \\ &\qquad\times (\ln\ln N)^{2/3}, \\ c &= \left(\frac{64}{9}\right)^{1/3}. \end{aligned}$$

This is subexponential in $n$ but superpolynomial. Shor replaces the best known classical asymptotic scaling with polynomial quantum gate complexity, subject to the structured-access and fault-tolerance assumptions.

Where the advantage does not come from

• It is not quantum parallelism followed by reading all values $a^x\bmod N$.
• It is not an exhaustive search over divisors.
• It is not the QFT in isolation; the periodic state and efficient modular arithmetic are indispensable.
• It is not a generic rule that quantum computers solve every hard problem exponentially faster.
• It does not remove input, verification, control, routing, or error-correction costs.

The speedup is an interference algorithm for a specific algebraic structure.

Cryptographic Implications

At cryptographically relevant scale on a fault-tolerant quantum computer, Shor’s algorithms target the mathematical assumptions behind widely deployed public-key systems:

Problem solved by Shor	Vulnerable constructions
integer factoring	RSA encryption, RSA key transport, and RSA signatures
finite-field discrete logarithm	finite-field Diffie–Hellman, ElGamal, and DSA
elliptic-curve discrete logarithm	ECDH, ECDSA, and related elliptic-curve protocols

Factoring an RSA modulus $N=pq$ reveals $p$ and $q$, from which the private exponent can be reconstructed. Solving $Q=xP$ on an elliptic curve reveals the private scalar $x$. These are direct breaks of the underlying one-way problems, not merely quadratic search improvements.

Shor’s algorithm does not directly break symmetric ciphers or cryptographic hash functions. Generic exhaustive key search is instead associated with Grover Search, which gives a quadratic query improvement under an appropriate coherent oracle model. Concrete cryptanalysis must still count reversible implementation, memory, parallelization, and error correction.

Post-quantum migration

Post-quantum cryptography consists of classical algorithms designed to resist known classical and quantum attacks; it does not require quantum communication or quantum hardware. In August 2024, NIST approved FIPS 203 for ML-KEM, FIPS 204 for ML-DSA, and FIPS 205 for SLH-DSA. Their publication is an operational basis for migration, not evidence that a cryptographically relevant quantum computer is imminent.

Migration can still be urgent because:

• cryptographic infrastructure changes slowly;
• archived ciphertext may remain sensitive for years;
• an adversary can store encrypted traffic now and attempt decryption later;
• protocols, certificates, hardware, and compliance regimes have long replacement cycles.

Quantum key distribution is a separate communication technology. It neither replaces the broad functionality of post-quantum public-key cryptography nor changes the mathematical statement of Shor’s algorithm.

Reading Resource Estimates Correctly

Asymptotic polynomial time does not determine the size of a useful machine. A resource estimate must specify at least:

1. the arithmetic circuit and success probability;
2. logical qubits, non-Clifford gates, depth, and measurements;
3. the error-correcting code and target logical failure rate;
4. physical error rates and operation times;
5. connectivity, routing, and classical reaction latency;
6. magic-state factories or another non-Clifford mechanism;
7. the space-time tradeoff and allowed wall-clock time.

Numbers quoted without this contract are not portable.

Three illustrative estimates

Compact logical circuit. Beauregard’s 2003 construction demonstrates that a fully general factoring circuit can use $2n+3$ qubits, at the price of $O(n^3\log n)$ gates. These are ideal logical qubits and elementary circuit operations. Error-correction overhead is outside the count.

Surface-code estimate from 2021. Gidney and Ekerå estimated that one particular construction could factor an RSA-2048 modulus in about eight hours using about 20 million physical qubits. Their model assumed a nearest-neighbor square grid, physical gate error $10^{-3}$, a $1\,\mu\mathrm{s}$ surface-code cycle, and $10\,\mu\mathrm{s}$ classical reaction time. At the abstract-circuit level, their formulas included

$$\begin{aligned} N_{\mathrm{logical}} &= 3n+0.002n\lg n, \\ N_{\mathrm{Toffoli}} &= 0.3n^3+0.0005n^3\lg n, \\ D_{\mathrm{meas}} &= 500n^2+n^2\lg n. \end{aligned}$$

The physical headline follows only after choosing the code layout, factories, error budget, and timing assumptions.

A 2025 preprint tradeoff. Gidney later estimated that RSA-2048 could be factored in less than a week with fewer than one million physical qubits under the same headline error, connectivity, cycle-time, and reaction-time assumptions. The reduction uses approximate residue arithmetic, yoked surface-code storage, and magic-state cultivation, while accepting a longer runtime and different arithmetic costs. This is a research preprint and a model-dependent estimate, not a hardware forecast. Its large shift from the 2021 number shows why resource estimates should be versioned and compared by assumptions, not repeated as timeless thresholds.

Elliptic-curve discrete logarithms

Roetteler, Naehrig, Svore, and Lauter gave a concrete reversible circuit for an elliptic curve over an $n$-bit prime field using at most

$$9n +2\left\lceil\log_2n\right\rceil +10$$

qubits and

$$448n^3\log_2n +4090n^3$$

Toffoli gates. This is again a logical gate-level estimate. The study indicates that elliptic-curve systems at comparable classical security can be a smaller quantum target than RSA, but a physical comparison still requires one consistent error-correction and hardware model.

No one of these studies supplies a universal “qubits required for Shor” number. They answer different architecture-and-runtime questions.

Why Fault Tolerance Dominates

Large modular-exponentiation circuits contain many sequential arithmetic operations. A small physical error rate per operation is not enough: the probability that the entire computation is correct must remain acceptable across a vast logical circuit.

A fault-tolerant implementation must budget:

• logical data storage: encoded registers must survive throughout modular exponentiation;
• non-Clifford operations: Toffoli, CCZ, or synthesized rotations usually consume distilled or cultivated resource states;
• factory throughput: too few factories save qubits but lengthen runtime;
• routing and connectivity: arithmetic operands and resource states must meet without uncontrolled congestion;
• code distance: the logical error per operation must be low enough for the total circuit volume;
• syndrome processing: decoding and feedforward must keep pace with code cycles;
• measurement latency: semiclassical QFT and adaptive arithmetic can depend on classical reactions;
• verification and retries: the physical estimate must include the algorithm’s stochastic success probability.

Changing any one item can move the physical-qubit count or runtime by orders of magnitude. This is why a small noisy demonstration and a cryptographically relevant fault-tolerant computation are different evidence categories, not merely different sizes of the same benchmark.

Universal Gate Sets explains logical synthesis and non-Clifford costs. Later pages on stabilizer codes and the surface code will own the error-correction mechanisms themselves.

What Small Demonstrations Do and Do Not Show

Small experiments can validate coherent modular arithmetic, phase kickback, semiclassical Fourier decoding, and control. They are valuable engineering and pedagogical tests.

However, factoring $15$ or another tiny number often permits aggressive compilation: identities specific to the chosen modulus, base, or known period remove most of the arithmetic. A demonstration that embeds information derived from the factors does not implement a scalable black-box factoring algorithm. Smolin, Smith, and Vargo showed how several apparently different small factoring demonstrations could be reproduced by an oversimplified procedure, emphasizing that valid evidence must not use the answer being sought.

For a scalable claim, ask:

• Does the circuit accept a general $n$-bit modulus rather than one hard-coded example?
• Is modular exponentiation implemented reversibly rather than replaced by a precomputed period?
• Are the factors absent from compilation and parameter selection?
• Does the resource count include precision, verification, and retries?
• Which components were demonstrated physically, simulated classically, or only estimated?

The evidence ladder in Claims, Hype, and Evidence Standards provides the broader reporting framework.

Common Mistakes

• Saying the quantum computer tries all factors and reads the correct one.
• Omitting the classical gcd and continued-fraction steps.
• Forgetting that the selected base can yield an odd order or the useless root $-1$.
• Assuming one phase sample always returns the full order.
• Applying continued fractions without verifying the candidate denominator.
• Treating controlled modular powers as unit-cost black boxes.
• Calling the QFT alone Shor’s algorithm.
• Reporting a logical-qubit count as a physical-qubit count.
• Quoting a physical estimate without its error rate, cycle time, connectivity, runtime, and code assumptions.
• Treating a compiled factor-$15$ circuit as evidence for scalable modular arithmetic.
• Claiming Shor breaks AES directly or solves all NP-complete problems.
• Presenting post-quantum migration as proof that a cryptographically relevant machine already exists.

End-to-End Checklist

Before evaluating a Shor implementation, record:

1. the exact factoring or group-discrete-logarithm problem;
2. classical preprocessing and random-base policy;
3. the reversible arithmetic circuit;
4. control-register precision and Fourier convention;
5. continued-fraction or hidden-subgroup postprocessing;
6. candidate verification and retry probability;
7. logical qubits, gate counts, depth, and non-Clifford volume;
8. error-correction, connectivity, timing, and factory assumptions;
9. the cryptographic parameter set and classical comparison;
10. which claims are theorem, simulation, experiment, estimate, or projection.

Exercises

1. Factor 15 from an order

For $N=15$ and $a=2$, determine the order $r$ and use it to recover both prime factors.

Solution

The powers modulo $15$ are

$$2,4,8,1,$$

so $r=4$. Since $r$ is even,

$$x=2^{r/2}=2^2=4.$$

Then

$$\gcd(x-1,15)=\gcd(3,15)=3$$

and

$$\gcd(x+1,15)=\gcd(5,15)=5.$$

Both gcds are nontrivial, giving $15=3\times5$.

2. Diagnose an unhelpful base

For $N=15$, choose $a=14$. Find its order and explain why the gcd step after order finding fails.

Solution

Since

$$14\equiv-1\pmod{15},$$

we have $14^2\equiv1\pmod{15}$ and therefore $r=2$. The order is even, but

$$x=14^{r/2}=14\equiv-1\pmod{15}.$$

Consequently

$$\gcd(x-1,15)=\gcd(13,15)=1$$

and

$$\gcd(x+1,15)=\gcd(15,15)=15.$$

Neither is a nontrivial factor. The run is recognized as unhelpful and a new base is chosen.

3. Verify the modular-multiplication eigenstate

Starting from

$$\lvert u_s\rangle = \frac1{\sqrt r} \sum_{k=0}^{r-1} e^{-2\pi isk/r} \lvert a^k\bmod N\rangle,$$

prove that $M_a\lvert u_s\rangle=e^{2\pi is/r}\lvert u_s\rangle$.

Solution

Apply $M_a$ and shift the summation index to $j=k+1$ modulo $r$:

$$\begin{aligned} M_a\lvert u_s\rangle &= \frac1{\sqrt r} \sum_{k=0}^{r-1} e^{-2\pi isk/r} \\ &\qquad\times \lvert a^{k+1}\bmod N\rangle \\ &= \frac1{\sqrt r} \sum_{j=0}^{r-1} e^{-2\pi is(j-1)/r} \\ &\qquad\times \lvert a^j\bmod N\rangle \\ &= e^{2\pi is/r} \lvert u_s\rangle. \end{aligned}$$

The wraparound term is valid because $a^r\equiv1\pmod N$.

4. Recover a denominator by continued fractions

Suppose order finding uses $Q=256$ and measures $y=73$. Show that $2/7$ is a convergent of $73/256$ and verify the rational-reconstruction error bound for denominator $7$.

Solution

The Euclidean algorithm gives

$$\frac{73}{256} = [0;3,1,1,36].$$

Its convergents include

$$0,\quad \frac13,\quad \frac14,\quad \frac27,\quad \frac{73}{256}.$$

The approximation error is

$$\left\lvert \frac{73}{256}-\frac27 \right\rvert = \frac1{1792} \approx5.58\times10^{-4}.$$

Since

$$\frac1{1792} < \frac1{2\cdot7^2} = \frac1{98},$$

Legendre’s sufficient condition holds. A candidate order $7$ must still be checked by testing $a^7\bmod N$.

5. Why use about twice the input bit length?

Let $r<N<2^n$ and choose $Q=2^{2n}$. Show that a nearest Fourier bin $y$ satisfies the continued-fraction accuracy condition for $s/r$.

Solution

A nearest integer to $Qs/r$ obeys

$$\left\lvert y-\frac{Qs}{r} \right\rvert \leq\frac12.$$

Dividing by $Q$ gives

$$\left\lvert \frac yQ-\frac sr \right\rvert \leq \frac1{2Q}.$$

Because $Q=2^{2n}$ and $N<2^n$,

$$Q>N^2>r^2.$$

Therefore

$$\left\lvert \frac yQ-\frac sr \right\rvert < \frac1{2r^2},$$

which is the desired sufficient condition.

6. A discrete-logarithm Fourier relation

In the group $\mathbb Z_7^\times$, let $g=3$ and $h=2$. First find $x$ such that $h=g^x$. Then check that the Fourier sample $(u,v)=(1,4)$ satisfies the hidden-subgroup relation $ux+v\equiv0\pmod6$.

Solution

The powers of $3$ modulo $7$ begin

$$3^1\equiv3, \qquad 3^2\equiv2.$$

Thus $x=2$ in the cyclic group of order $6$. For the sample $(1,4)$,

$$ux+v = 1\cdot2+4 = 6 \equiv0 \pmod6.$$

Because $u=1$ is invertible,

$$x \equiv -vu^{-1} \equiv -4 \equiv2 \pmod6.$$

7. Separate algorithmic and physical claims

Classify each statement as a theorem-level algorithmic claim or an assumption-dependent engineering estimate:

1. factoring has a polynomial-time quantum algorithm;
2. a general circuit can be built with $2n+3$ logical qubits;
3. RSA-2048 can be factored in eight hours with 20 million physical qubits;
4. fewer than one million physical qubits can suffice if a runtime below one week is accepted.

Explain what extra information is required to compare statements 3 and 4.

Solution

Statement 1 is the asymptotic algorithmic theorem. Statement 2 is a logical circuit construction with a particular gate and depth tradeoff. Statements 3 and 4 are physical resource estimates derived from selected arithmetic, code, layout, error, timing, factory, and failure-budget models.

To compare 3 and 4, one must align the physical gate error, code-cycle time, classical reaction time, connectivity, error-correcting code, arithmetic method, logical failure target, magic-state method, number of factories, retry policy, and wall-clock constraint. A smaller qubit count may be purchased with greater depth or runtime, so the two headline numbers alone do not establish an across-the-board improvement.

References

• P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Journal on Computing 26, 1484–1509, 1997, doi:10.1137/S0097539795293172.
• A. Ekert and R. Jozsa, “Quantum computation and Shor’s factoring algorithm,” Reviews of Modern Physics 68, 733–753, 1996, doi:10.1103/RevModPhys.68.733.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary ed., Cambridge University Press, 2010, doi:10.1017/CBO9780511976667.
• J. P. Buhler, H. W. Lenstra Jr., and C. Pomerance, “Factoring integers with the number field sieve,” in The Development of the Number Field Sieve, 50–94, 1993, doi:10.1007/BFb0091539.
• S. Beauregard, “Circuit for Shor’s algorithm using $2n+3$ qubits,” Quantum Information and Computation 3, 175–185, 2003, doi:10.26421/QIC3.2-8.
• M. Roetteler, M. Naehrig, K. M. Svore, and K. Lauter, “Quantum resource estimates for computing elliptic curve discrete logarithms,” in Advances in Cryptology – ASIACRYPT 2017, 241–270, 2017, doi:10.1007/978-3-319-70697-9_9.
• C. Gidney and M. Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,” Quantum 5, 433, 2021, doi:10.22331/q-2021-04-15-433.
• C. Gidney, “How to factor 2048 bit RSA integers with less than a million noisy qubits,” 2025 research preprint, arXiv:2505.15917.
• J. A. Smolin, G. Smith, and A. Vargo, “Oversimplifying quantum factoring,” Nature 499, 163–165, 2013, doi:10.1038/nature12290.
• National Institute of Standards and Technology, “Announcing approval of three Federal Information Processing Standards for post-quantum cryptography,” August 13, 2024, NIST announcement.

See Also

• Quantum Phase Estimation
• Algorithmic Primitives
• Quantum Complexity Classes
• Grover Search
• Circuit Model
• Universal Gate Sets
• Resource Estimation
• Resource Estimation Tools
• Claims, Hype, and Evidence Standards