thinQmaster Virtual testing partner Adaptive practice exams that find your weak spots and drill them. Every answer explained. From $69
Enroll

thinQmaster

Find your exam

Five questions free, before you decide.

Step 1 · choose a vendor

In one of our camps? Your practice exams come with the tuition — they are on your study page already.

Security Fundamentals & Crypto · Advanced

Shor's Algorithm

Quantum algorithm that efficiently factors integers and computes discrete logarithms, breaking RSA, DH, and ECC.

Definition

Published by Peter Shor in 1994, the algorithm provides exponential speedup over the best known classical methods for factoring and discrete logs. A sufficiently large fault-tolerant quantum computer running it would break all widely deployed public key cryptography. It is the primary motivation for post-quantum cryptography.

Example

RSA-2048 that would take classical computers billions of years could be factored by a large CRQC running Shor's algorithm.

Exam tip

Shor breaks asymmetric crypto; Grover only weakens symmetric crypto and hashes.

Related terms