Skip to content
LSLab

How Does Shor's Algorithm Link Factoring to Period Finding?

  • Basic
  • Article
  • Ages 16+
  • 6 min read
Metal spheres arranged in equal rows and columns beside a small chip package.

Shor’s algorithm links two problems: factoring a number into primes, and finding the period of a periodic function. Shor found that the first problem reduces to the second, and a quantum computer is thought to solve the second efficiently. That lets it factor large numbers faster than any known classical algorithm.

Contents
A large number is split into two factors through an intermediate step that is periodic.
  • Large number to factor
  • Period-finding step (wavy line)
  • Two factors

What you will learn

  • State what the factoring problem is and why it matters to cryptography.
  • Describe how Shor’s algorithm reduces factoring to period finding.
  • Separate what the algorithm can do in theory from what machines have done so far.

Before you start

It helps to read How Do Quantum Computers Process Information? first. Other terms are explained as they appear.

What is the factoring problem, and why does it matter?

It is the problem of finding the primes that multiply to a given number, and it sits at the heart of many cryptographic protocols. According to the Stanford Encyclopedia of Philosophy, general interest in quantum computing was initially triggered by P. W. Shor in 1994. He showed how a quantum algorithm apparently can factor large numbers into primes far more efficiently than any known classical algorithm.

The Stanford source says factoring lies at the heart of widely used cryptographic protocols such as RSA. Nobody knows how to classically factor numbers into primes in polynomial time, and the best classical algorithms we have for this problem are sub-exponential.

That is why the discovery that quantum computers can solve factoring in polynomial time has had a dramatic effect.

The best classical route known winds around, while reducing to period finding offers a more direct route.
  • Large number to factor
  • Factors to find
  • Classical route: long and winding
  • Route through period finding: more direct

How does Shor turn factoring into period finding?

Shor’s result rests on the discovery that the problem of factoring reduces to the problem of finding the period of a certain periodic function. The Stanford source describes this as an ingenious number-theoretic argument.

The main steps run as follows.

  1. Pick a number at random that is smaller than the number to factor and has no common factors with it other than one.
  2. Take a periodic function built from powers of that number, with remainders taken against the number to be factored. Find the period of this function.
  3. Once the period is known, the original number can be factored, provided the period is even and one further condition holds. If the condition fails, pick another number and try again.
  4. The factors are the greatest common divisors of a number derived from the period and the original number, found in polynomial time with the well-known Euclidean algorithm.

The part a quantum computer takes on is step 2. According to the Stanford source, that a quantum computer can solve this problem efficiently is hinted at by Simon’s algorithm, which handles a more restricted case of periodic functions.

Choose a number, form a periodic function, use the quantum subroutine to find its period, then derive factors.
  • Step one: pick a random number
  • Step two: the periodic function
  • Step three: the period (ruler)
  • Step four: the factors

Can Shor break encryption right now?

The algorithm alone does not establish that. Breaking a practical key requires demonstrating a sufficiently large and reliable computation. According to the Stanford source, implementing Shor’s algorithm on a large-scale quantum computer would render ineffective the widely used cryptosystems that rely on the premise that no efficient algorithm for factoring exists.

A small-number example in a reference should not be presented as a current record. The important distinction is between an efficient algorithm on an ideal model and hardware sufficiently large and reliable to run it against practical cryptographic keys.

On the response side, according to a NIST news release, NIST began selecting and standardizing quantum-resistant algorithms in 2015. The algorithms it standardized are based on different math problems that would stymie both conventional and quantum computers.

Breaking encryption needs a far larger machine than the small ones today, and quantum-resistant standards are the shield.
  • Large-scale machine that would be needed (dashed frame)
  • The small machine that exists
  • Quantum-resistant standards (shield)

Real-world example

Think of a wheel turning steadily with one mark on it. To learn how long it takes the mark to return to its starting spot, you only need the period of the turn, not each separate revolution. Shor does something similar with a periodic function: find the period, then work out the factors.

This is an intuition-building picture of the idea of a period, not how a quantum computer actually computes.

Common misunderstandings

Shor’s algorithm does not try divisors one by one. It reduces the problem to finding a period and then uses mathematical steps to get the factors.

Shor does not mean every cryptosystem is broken. The factoring result threatens systems relying on that problem, such as RSA; it does not establish insecurity for every cryptographic algorithm.

Quantum computers have not been proven superior in every way. The Stanford source says no proof exists of general superiority.

Frequently asked questions

What does Shor’s algorithm do?

It factors large numbers into primes by reducing the problem to finding the period of a periodic function.

Why does Shor matter for cryptography?

Factoring lies at the heart of many widely used cryptographic protocols, such as RSA.

Has Shor broken RSA yet?

An algorithmic result is not evidence of breaking a practical RSA key. The key requirement is a sufficiently large and reliable computation; a small-number demonstration does not establish that.

Is there a response?

NIST has standardized algorithms based on math problems hard for both ordinary and quantum computers.

Summary

  • Shor reduces factoring to finding the period of a periodic function.
  • Period finding is the part a quantum computer is thought to do efficiently.
  • Breaking encryption needs a large machine, and NIST has standardized quantum-resistant algorithms.

Terms in this article

English and Vietnamese terms, with the meanings used here. Hover, tap or Tab to a term with a dotted underline for an explanation as you read.

Shor's algorithmthuật toán Shor
A quantum algorithm that factors large numbers into primes by reducing the problem to period finding.
factoringphân tích thừa số
The problem of finding the primes that multiply to a given number.
periodchu kỳ
The interval at which a periodic function repeats.
RSA
A widely used cryptographic protocol that rests on the difficulty of factoring.
Euclidean algorithmthuật toán Euclid
The well-known method for finding greatest common divisors in polynomial time.

This article is not marked as viewed

Spotted something wrong or unsafe?

Tell the administrator by email. The message already has the article title and address.

Report this article

More in this topic

  • A beam-splitter cube and mirror mounts on an optical bench with a fine red laser beam.
    Basic

    What Is Quantum Superposition?

    Understand superposition, measurement and qubits through a thought experiment, without assuming every possible result can be read at once.

    5 min read
  • A trapped-ion vacuum apparatus with a small glowing centre next to a conventional small memory board on a bright optical bench, close three-quarter view.
    Basic

    How Does a Qubit Differ from a Bit?

    Compare bits and qubits through states, measurement and use; avoid mistaking a qubit for a memory cell whose possible answers can all be read at once.

    3 min read
  • Two qubit structures on a chip connected by a metallic coupling trace.
    Basic

    How Does CNOT Link Control and Target Qubits?

    CNOT is a two-qubit gate that flips or keeps the target by the control qubit. See why it is a building block and how it differs from a measurement.

    6 min read
  • Two separated optical stations with a beam splitter, detectors and connecting optical fiber.
    Basic

    Why Does Teleportation Need a Classical Channel?

    Quantum teleportation needs a shared entangled pair and two bits sent over an ordinary channel. See each step and why it fails without the message.

    6 min read
See all articles of the topic

Sources

These sources are written for older readers. If they feel hard, read them with an adult.