Shor’s Factoring Algorithm

Factoring combines quantum and classical work

Shor’s factoring algorithm finds nontrivial factors of a composite integer. The quantum part obtains an order in modular arithmetic. Classical preprocessing chooses a useful instance, and classical postprocessing turns a suitable order into factors. The complete algorithm is therefore a hybrid mathematical procedure, not a single Fourier circuit that measures two prime numbers directly.

Read order finding first. Useful classical prerequisites are modular exponentiation and the Euclidean algorithm for greatest common divisors. A nontrivial factor is a divisor greater than one and smaller than the original number. Factoring and testing whether a number is prime are different tasks.

WORKED DIAGRAM · A14Factor fifteen using base two

A suitable even order produces a nontrivial square root of one modulo fifteen. Base fourteen instead has order two but yields only trivial gcds, so the algorithm retries.

The problem and input size

The input is an ordinary classical integer N. The goal is to return a nontrivial factor when N is composite, with a controlled success probability. The size parameter is approximately the number of binary digits of N. A polynomial algorithm in that size is very different from trying every integer up to N.

Handle easy cases classically first. An even N has factor two. Perfect powers can be recognised and reduced to smaller tasks. For the main quantum reduction, consider an odd composite that is not a prime power. Choose an integer a between one and N and compute its greatest common divisor with N. If that divisor is nontrivial, the factor has already been found without a quantum call.

The quantum subroutine

If a is coprime to N, find its order r: the smallest positive exponent returning one modulo N. Quantum phase estimation on reversible modular multiplication supplies samples from which r can be reconstructed and verified. The easy initial modular state is a superposition of relevant eigenstates, so repeated phase samples and classical processing may be required.

The modular arithmetic dominates much of the circuit engineering. Controlled powers exploit repeated squaring and structured reversible multiplication. They should not be implemented by blindly repeating one base operation an exponentially large number of times. Equally, a demonstration that hard-codes a known small period is not a scalable implementation of unknown order finding.

Turn an even order into factors

If r is even, set x to a raised to half r modulo N. Then x squared is one modulo N. Therefore N divides the product of x minus one and x plus one. If x is neither plus one nor minus one modulo N, those two neighbouring expressions can share different nontrivial factors with N. Compute their greatest common divisors with N.

If r is odd, this route does not apply. If x is minus one modulo N, the gcds are trivial. Retry with another base. A correctly verified order should not give x equal to plus one for a positive even minimal r, since that would contradict minimality. The usual success analysis shows that random suitable choices provide a useful constant success probability for the standard class of composite inputs, with repetition increasing confidence.

Work N equal to fifteen

Choose a equal to two. Its greatest common divisor with fifteen is one. The powers cycle through two, four, eight and one, so r is four. Half the order is two, giving x equal to four. The two gcd calculations are

$$\gcd(4-1,15)=3,\qquad \gcd(4+1,15)=5.$$

Both are nontrivial factors, and multiplying them checks the result. The quantum subroutine’s purpose was to expose the order four, not to output three and five directly. The final arithmetic is entirely classical and cheap for this tiny example.

Now choose a equal to fourteen, which is negative one modulo fifteen. Its order is two, but x is fourteen, also negative one modulo fifteen. The gcds of thirteen and fifteen, and fifteen and fifteen, are one and fifteen. This attempt produces no nontrivial factor. Finding an even order is necessary for this route but is not sufficient on its own.

Why the reduction is useful

The identity x squared equal to one modulo N can have nontrivial solutions when N is composite. Modular order finding supplies a way to encounter such a solution. The classical random choice makes it likely to find a helpful case after a manageable number of attempts. The proof combines number theory with the quantum order-finding guarantee.

Do not infer that factoring is classically proven to require exponential time. No polynomial-time classical factoring algorithm is known in the conventional model, and the best known classical methods have a different asymptotic form. Shor establishes a polynomial-time quantum algorithm; an exact unconditional separation from all possible classical factoring algorithms is a stronger statement than the known result.

What the speedup includes and leaves out

The theoretical algorithm uses a number of ideal operations polynomial in the bit-length, with sufficiently accurate arithmetic and phase estimation. Practical execution requires logical reliability over a long coherent calculation. Physical qubits, runtime, error correction, control, routing and resource-state production depend on architecture and error assumptions. A small compiled demonstration cannot establish those resources for a large input.

RSA’s security relevance comes from its mathematical dependence on factoring-related structure, but the existence of Shor’s algorithm is different from possession of a device capable of running it at a cryptographic scale. Resource estimates must be read with their assumptions and dates. The book’s hardware chapter discusses that distinction separately from this correctness proof.

Shor also gave a quantum algorithm for discrete logarithms, a related algebraic task with a different reduction. It is not the same as applying the factoring gcd steps to every public-key scheme. Understanding which mathematical problem underlies a cryptosystem is essential before drawing an algorithmic conclusion about it.

A sound learning experiment

Work several small bases for fifteen or twenty-one by hand. Record the initial gcd, the order, whether it is even, the half-order power and the final gcds. Mark failed attempts honestly. Then study a modular arithmetic circuit that computes the order without inserting the known answer into its construction. This separates a correctness illustration from a scalable implementation claim.

Exercises

1. For N fifteen and a equal to four, find the order and perform the factor extraction.

2. A report says, “An even order always gives factors.” Use the base fourteen example to correct the statement.

Worked answers

1. Four squared is sixteen, congruent to one modulo fifteen, so r is two. The half-order power is four. The gcds are three and five, giving the factors.

2. An even order must also yield a half-order power other than minus one modulo N. For base fourteen, r is two but the half-order power is minus one, so the gcds are one and fifteen. The algorithm must retry with another base when the extraction conditions fail.

Sources

Shor’s primary paper presents the polynomial-time quantum factoring and discrete-logarithm algorithms. IBM’s Shor derivation gives a guided order-finding reduction.

Check your understanding

PAUSE & THINK

Why does base fourteen fail to factor fifteen through the half-order step?

Choose your answer

Its order is oddThe half-order power is −1 modulo fifteenFourteen and fifteen share a factor

Check my answer

Answer: The half-order power is −1 modulo fifteen. The order is two and the half-order power is fourteen, or −1 modulo fifteen. The resulting gcds are one and fifteen, so no nontrivial factor is obtained.