---
title: "Shor's Algorithm"
description: "A quantum computing game-changer"
url: https://help.terraquantum.io/en/articles/146-shor-s-algorithm
collection: "Quantum algorithms"
updated: 2025-08-06
language: en
---

# Shor's Algorithm

A quantum computing game-changer

Shor's algorithm, developed by mathematician Peter Shor in 1994, is a quantum algorithm designed for integer factorization, which is the process of breaking down a composite number into its prime factors. This algorithm is significant because it can solve this problem exponentially faster than the best-known classical algorithms.

### Key Concepts:

1.  **Quantum Computing Basics**: Quantum computers leverage the principles of quantum mechanics, such as superposition and entanglement, to perform calculations in ways that classical computers cannot. Quantum bits, or qubits, can represent both 0 and 1 simultaneously, allowing quantum computers to process a vast number of possibilities at once.
    
2.  **Integer Factorization**: The problem Shor’s algorithm addresses is finding the prime factors of a large composite number NNN. For instance, factoring 15 into 3 and 5 is straightforward, but factoring a large number, like those used in RSA encryption (which are hundreds of digits long), is computationally intensive and time-consuming with classical computers.
    

### Shor's Algorithm Process:

1.  **Quantum Fourier Transform (QFT)**: Shor’s algorithm employs the QFT, a quantum analog of the classical discrete Fourier transform, which helps identify periodicity in a function, a crucial step in factorization.
    
2.  **Period Finding**: The algorithm transforms the factorization problem into a problem of finding the period of a specific mathematical function related to _N_. This period-finding task is where the quantum speedup occurs.
    
3.  **Classical Post-processing**: After the quantum part, classical computing methods are used to derive the factors from the period found.
    

ADD QFT ARTICLE

### Significance:

Shor’s algorithm demonstrated that a quantum computer could solve certain problems exponentially faster than classical computers. Specifically, it can factorize integers in polynomial time, compared to the best classical algorithms which require super-polynomial time. This has profound implications for cryptography, particularly for RSA encryption, which relies on the difficulty of factoring large integers as a security foundation. If large-scale, fault-tolerant quantum computers are built, they could potentially break current encryption schemes, necessitating a shift to quantum-resistant cryptographic methods.

Shor’s algorithm remains one of the most celebrated achievements in quantum computing, showcasing the potential of quantum technology to revolutionize fields dependent on computational complexity.