Shor's algorithm and Grover's algorithm are the two most consequential quantum algorithms ever devised, and they threaten modern cryptography in fundamentally different ways. Shor's algorithm, published by Peter Shor in 1994, factors large integers exponentially faster than the best known classical methods, collapsing the mathematical assumptions behind public-key systems such as RSA and elliptic-curve cryptography. Grover's algorithm, devised by Lov Grover in 1996, delivers only a quadratic speedup for unstructured search, which means it weakens symmetric encryption like AES rather than breaking it outright. Understanding that distinction—exponential versus quadratic, broken versus merely eroded—is the key to reading the quantum threat landscape correctly.

Introduction to Quantum Algorithms: Shor's and Grover's

Classical computers process information as bits that are definitively 0 or 1, whereas quantum computers use qubits that can exist in superpositions of states. As Fortinet's security analysis explains, this enables quantum machines to solve some mathematical problems exponentially faster than traditional computing methods, and the two algorithms that pose the most significant threat to modern cryptographic systems are Shor's and Grover's. The practical consequence of that difference in scale is stark: an exponential speedup turns a computationally infeasible task into a feasible one, while a quadratic speedup merely reduces the cost of an attack by a factor related to the square root of the search space.

It is worth noting that neither algorithm is a monolithic quantum program. In both cases, a classical computer handles parts of the processing—preparing inputs and performing post-processing—while the quantum computer runs the core subroutine that exploits superposition, entanglement, and interference. The algorithms differ in what that quantum core actually computes, and that difference determines everything about their cryptographic impact.

Shor's Algorithm: Factoring and Period-Finding

Shor's algorithm solves the integer factorization problem: given a large number N, find non-trivial factors p and q such that N = pq. Classically, the best-known algorithms for this task are sub-exponential but still very slow for cryptographic sizes; the best classical factoring algorithm, the General Number Field Sieve, runs in sub-exponential time, which remains impractical to reverse for the enormous numbers used in real systems. Shor's algorithm, by contrast, runs in polynomial time in log N—an exponential improvement over anything classical computers can achieve.

The key trick, as technical accounts of the algorithm describe it, is that Shor's algorithm does not factor directly. Instead, it reduces factoring to a period-finding problem and then uses a quantum subroutine to find that period efficiently. The classical pre-processing picks a random integer a and computes the greatest common divisor of a and N; if that divisor is not 1, a non-trivial factor has already been found. Otherwise, the quantum subroutine takes over to find the period of a related function, and classical post-processing converts that period into the factors. Ronald de Wolf's lecture materials on the main quantum algorithms note that this exponential speedup over the best known classical algorithm is precisely what "breaks a lot of public-key cryptography."