Meta tags:
description= How Shor s algorithm breaks RSA encryption by factoring large numbers exponentially faster than any classical computer, and what this means for…;
author= QuantumComputingCourses.com;
Headings (most frequently used words):
factoring, shor, algorithm, to, explained, integer, factorization, how, breaks, rsa, reduces, period, finding, full, structure, modular, exponentiation, 15, small, example, related, tutorials, get, one, quantum, email, week, ready, go, deeper, learn, reference, careers, about,
Text of the page (most frequently used words):
the (70), quantum (55), #algorithm (35), and (29), for (29), shor (24), gcd (22), factoring (20), this (19), rsa (13), read (13), #period (13), courses (12), mod (12), classical (11), guide (10), qiskit (10), with (10), qubits (10), which (10), from (9), tutorials (9), finding (9), not (9), that (9), qubit (8), min (8), qft (8), using (8), about (7), all (7), computing (7), modular (7), physical (7), log (7), post (6), hardware (6), how (6), exponentiation (6), circuit (6), large (6), fourier (6), transform (6), return (6), import (6), register (6), 2026 (5), com (5), free (5), algorithms (5), time (5), intermediate (5), reduces (5), breaks (5), integer (5), these (5), first (5), you (5), found (5), process (5), find (5), current (5), however (5), error (5), can (5), are (5), computers (5), 2048 (5), operations (5), factor (5), step (5), input (5), number (5), bloch (4), sphere (4), framework (4), learning (4), zeitgeist (4), donovan (4), entanglement (4), small (4), example (4), full (4), structure (4), factorization (4), next (4), since (4), task (4), uses (4), security (4), millions (4), cryptography (4), two (4), speedup (4), its (4), grover (4), fips (4), range (4), running (4), text (4), rangle (4), bit (4), hello (4), world (4), use (3), policy (3), amazon (3), team (3), careers (3), programming (3), timeline (3), types (3), glossary (3), case (3), studies (3), writes (3), what (3), cirq (3), pennylane (3), week (3), one (3), any (3), implementing (3), real (3), level (3), browse (3), ibm (3), out (3), have (3), prime (3), exponential (3), problem (3), cryptographic (3), exponentially (3), faster (3), discrete (3), computer (3), encryption (3), dsa (3), different (3), problems (3), only (3), search (3), 2024 (3), formerly (3), based (3), google (3), correction (3), when (3), requires (3), result (3), part (3), none (3), factor2 (3), factor1 (3), math (3), factors (3), quantumcircuit (3), bmod (3), gates (3), every (3), non (3), trivial (3), superposition (3), measure (3), apply (3), swap (3), angle (3), cannot (3), explained (3), braket (3), cookies (2), experience (2), affiliate (2), terms (2), hadamard (2), quantumcomputingcourses (2), books (2), podcasts (2), events (2), faq (2), editorial (2), jobs (2), interview (2), certifications (2), salary (2), reference (2), news (2), frameworks (2), paths (2), learn (2), written (2), who (2), research (2), industry (2), references (2), tools (2), quantumcomputing (2), 112 (2), email (2), get (2), reaching (2), point (2), bernstein (2), vazirani (2), hidden (2), string (2), finder (2), bell (2), inequalities (2), chsh (2), test (2), know (2), related (2), python (2), language (2), beginner (2), guides (2), coursera (2), edx (2), udemy (2), brilliant (2), was (2), tutorial (2), has (2), because (2), there (2), make (2), had (2), also (2), remains (2), scales (2), then (2), ecc (2), rely (2), logarithms (2), long (2), response (2), involves (2), standards (2), such (2), years (2), decades (2), requiring (2), corrected (2), kem (2), provides (2), while (2), practically (2), today (2), noisy (2), attacks (2), mathematical (2), does (2), nist (2), module (2), lattices (2), 205 (2), crystals (2), 204 (2), 203 (2), prepare (2), challenge (2), demonstrated (2), below (2), been (2), break (2), resource (2), requirements (2), several (2), gidney (2), million (2), gate (2), shors_classical_part (2), try (2), extract (2), def (2), even (2), calculate (2), greatest (2), equals (2), finally (2), processing (2), must (2), function (2), perform (2), preprocessing (2), select (2), depth (2), most (2), numbers (2), compute (2), equivalent (2), check (2), measurement (2), output (2), collapses (2), states (2), pick (2), random (2), ordering (2), controlled (2), phase (2), applied (2), each (2), amplitudes (2), performs (2), high (2), probability (2), domain (2), fast (2), polynomial (2), key (2), primes (2), cybersecurity (2), concepts (2), prerequisites (2), wave (2), accept, decline, improve, your, track, performance, see, our, cookie, privacy, disclosure, llc, associate, earn, qualifying, purchases, contact, site, talent, pool, job, training, questions, cheatsheets, history, docs, compare, maintained, curated, anyone, 241, 220, subscribe, address, new, worth, taking, changed, spam, unsubscribe, anytime, katas, self, paced, exercises, microsoft, paid, advanced, data, structures, boulder, university, cambridge, jun, updated, glance, page, getting, started, superstaq, networking, swapping, repeaters, previous, continue, structured, more, ready, deeper, share, yes, helpful, quantumzeitgeist, ran, his, 2018, put, subject, down, built, material, forced, choice, nobody, should, pop, science, hand, waving, end, phd, physics, ramp, other, code, usually, stopped, working, begins, integers, classically, intractable, solution, diffie, hellman, difficulty, understanding, essential, assessing, term, implications, deploying, capable, breaking, away, advantage, summary, represent, applying, like, impact, severe, conversely, quadratic, applicable, unstructured, effectively, halves, symmetric, keys, compatible, devices, too, deep, partially, implemented, spaces, neither, useful, nisq, scale, versus, believed, resist, both, including, those, stems, fact, they, help, solve, standardized, three, sphincs, hash, functions, slh, dilithium, kyber, threat, immediate, development, finalized, specifically, face, significant, limitations, systems, 100, 000, improving, fidelity, threshold, surface, codes, scaling, gap, between, technology, ability, measured, substantial, estimates, call, thousand, logical, translates, accounting, widely, cited, ekera, 2019, analysis, estimated, hours, 2025, update, brought, estimate, under, around, print, pow, given, attempt, transpile, aersimulator, qiskit_aer, complex, shows, simplified, value, yielding, determine, common, divisor, cases, second, confirm, times, tackle, proceed, let, trace, required, accounts, used, explains, why, cryptographically, relevant, considering, goal, simultaneously, operation, evaluating, possible, once, achieve, need, efficient, reversible, multiplication, deeply, implement, rightarrow, faces, repeat, odd, continued, fractions, multiple, inverse, same, uniform, got, lucky, done, correct, numpy, conceptually, steps, rotations, subsequent, repeated, reversed, acts, encoding, transformation, limitation, state, interference, appear, dft, converts, sequence, frequency, revealing, periodic, patterns, fft, conversion, enough, finds, least, smallest, equiv, pmod, where, accidentally, complete, reduction, proceeds, follows, directly, instead, handle, efficiently, rests, assumption, back, into, computationally, infeasible, publish, public, 3233, practice, 1024, bits, generate, straightforward, relies, simple, asymmetry, multiplying, easy, but, their, product, hard, consider, easily, now, imagine, roughly, 617, decimal, digits, impossible, methods, best, known, general, field, sieve, order, modulus, earth, big, bang, would, remain, reach, changes, solves, makes, important, sections, linear, algebra, basics, proficiency, shors, than, means, jan, series, home, troubleshooting, prep, universities, career, cheat, sheets, migration, comparison, pinball, explore, ocean, tket, pyquil, rigetti, quera, azure, quantinuum, ionq, providers, course, platforms, skip, main, content,
Text of the page (random words):
shor s algorithm explained skip to main content quantumcomputing courses com courses all courses course platforms coursera edx udemy brilliant hardware providers google quantum ai ibm quantum ionq quantinuum amazon braket azure quantum quera rigetti d wave tutorials all tutorials hello world qiskit hello world cirq hello world pennylane hello world braket quantum gates grover s algorithm shor s algorithm reference all frameworks qiskit cirq pennylane amazon braket pyquil tket d wave ocean q explore learn learning paths prerequisites programming guide case studies glossary books quantum news podcasts tools bloch sphere quantum pinball guides algorithm guide hardware guide qubit types framework comparison migration guide language timeline cheat sheets career events 2026 jobs careers certifications salary guide universities interview prep faq troubleshooting about about team search browse courses home tutorials shor s algorithm explained concepts intermediate free 12 60 in series 20 min read 31 jan 2026 by dr donovan quantum zeitgeist editorial policy shor s algorithm explained how shor s algorithm breaks rsa encryption by factoring large numbers exponentially faster than any classical computer and what this means for cybersecurity shors algorithm integer factoring quantum fourier transform rsa cryptography quantum algorithms period finding prerequisites python proficiency beginner quantum computing concepts superposition entanglement linear algebra basics in this guide 6 sections 01 integer factorization 02 how factoring breaks rsa 03 factoring reduces to period finding 04 full shor s algorithm structure 05 modular exponentiation 06 factoring 15 a small example integer factorization consider the number 15 its prime factors are easily found 3 5 now imagine a 2048 bit number roughly 617 decimal digits long finding its prime factors is practically impossible using classical methods the best known classical algorithm the general number field sieve requires on the order of 2 112 operations for a 2048 bit modulus even if every computer on earth had been running since the big bang factoring a 2048 bit number would remain out of reach shor s algorithm changes this it solves the problem in polynomial time requiring only about o log n ³ quantum operations this exponential speedup makes shor s algorithm the most important quantum algorithm for cybersecurity how factoring breaks rsa rsa encryption relies on a simple mathematical asymmetry multiplying two large primes is easy but factoring their product is hard to generate an rsa key the process is straightforward select two large primes p 61 q 53 in practice these are about 1024 bits each calculate n p q 3233 publish n as part of the public key the security of rsa rests on the assumption that factoring n back into p and q is computationally infeasible classical computers cannot perform this task for large n quantum computers however running shor s algorithm can factoring reduces to period finding shor s algorithm does not factor a number directly instead it reduces the problem of factoring to period finding a task that quantum computers can handle efficiently the reduction proceeds as follows step 1 pick a random integer a where 1 a n and gcd a n 1 if gcd 1 you have accidentally found a factor and the process is complete step 2 find the period r of the function f x aˣ mod n find the smallest r r r such that a r 1 m o d n a r equiv 1 pmod n a r 1 mod n step 3 with high probability at least one of these is a non trivial factor gcd a r 2 1 n gcd a r 2 1 n classical computers cannot find r r r fast enough for large n n n the quantum part of shor s algorithm finds r r r in polynomial time using the quantum fourier transform qft the classical discrete fourier transform dft converts a sequence in the time domain to the frequency domain revealing periodic patterns the fast fourier transform fft performs this conversion using o n log n o n log n o n lo g n operations the quantum fourier transform qft acts on quantum states encoding amplitudes it performs the equivalent transformation using only o log n 2 o log n 2 o lo g n 2 operations which is exponentially faster however there is a limitation measurement collapses the state so you cannot read out all the amplitudes what you can do is use interference to make the period r r r appear with high probability when you measure conceptually the qft circuit for n n n qubits involves several steps first a hadamard gate is applied to the first qubit next controlled phase rotations of angle π 2 k pi 2 k π 2 k are applied to each subsequent qubit this process is then repeated for every qubit finally the qubit ordering must be reversed using swap gates qiskit qft on n qubits from qiskit import quantumcircuit import numpy as np def qft n qc quantumcircuit n for j in range n qc h j for k in range j 1 n angle np pi 2 k j qc cp angle k j controlled phase swap qubits to correct bit ordering for j in range n 2 qc swap j n j 1 return qc full shor s algorithm structure classical preprocessing 1 pick random a 1 a n 2 check gcd a n if 1 we got lucky done quantum period finding 3 prepare 0 0 input register output register 4 apply h ⁿ to input register uniform superposition 5 apply modular exponentiation x 0 x aˣ mod n 6 measure output register collapses input to states with same aˣ mod n 7 apply inverse qft to input register 8 measure input register get a multiple of n r classical post processing 9 use continued fractions to extract r from measurement 10 compute gcd a r 2 1 n 11 check if result is a non trivial factor 12 repeat if r is odd or a r 2 1 mod n modular exponentiation implementing shor s algorithm faces its greatest challenge in step 5 modular exponentiation the goal is to compute x 0 x a x m o d n x rangle 0 rangle rightarrow x rangle a x bmod n rangle x 0 x a x mod n for all x x x in superposition simultaneously this quantum circuit operation is the quantum equivalent of evaluating f x a x m o d n f x a x bmod n f x a x mod n for every possible x x x at once to achieve this we need an efficient reversible quantum circuit for modular multiplication a task that is deeply non trivial to implement on current hardware the circuit depth required for modular exponentiation scales as o log n 3 o log n 3 o lo g n 3 this depth accounts for most of the quantum gates used in shor s algorithm which explains why factoring cryptographically relevant numbers requires millions of physical qubits when considering error correction factoring 15 a small example let s trace shor s algorithm using n 15 n 15 n 15 first we perform classical preprocessing we select a 7 a 7 a 7 since gcd 7 15 1 gcd 7 15 1 g cd 7 15 1 we can proceed next we tackle the quantum period finding step we must find r r r for the function f x 7 x m o d 15 f x 7 x bmod 15 f x 7 x mod 15 7¹ mod 15 7 7² mod 15 4 7³ mod 15 13 7 mod 15 1 period r 4 classical post processing the value of r is 4 which is even we calculate 7 4 2 7 4 2 7 4 2 yielding 7 2 49 7 2 49 7 2 49 next we determine the greatest common divisor for two cases first gcd 49 1 15 gcd 48 15 text gcd 49 1 15 text gcd 48 15 gcd 49 1 15 gcd 48 15 which equals 3 second gcd 49 1 15 gcd 50 15 text gcd 49 1 15 text gcd 50 15 gcd 49 1 15 gcd 50 15 which equals 5 finally we confirm the factorization of 15 15 3 5 15 3 times 5 15 3 5 simplified shor s for n 15 using qiskit the full circuit is complex this shows the structure from qiskit import quantumcircuit from qiskit_aer import aersimulator from qiskit import transpile import math def shors_classical_part n a r given period r attempt to extract factors if r 2 0 return none try different a x pow a r 2 n if x n 1 return none try different a factor1 math gcd x 1 n factor2 math gcd x 1 n if factor1 not in 1 n return factor1 if factor2 not in 1 n return factor2 return none for n 15 a 7 r 4 found by quantum part result shors_classical_part 15 7 4 print f factor found result 3 or 5 resource requirements for real cryptographic attacks to break rsa 2048 using shor s algorithm the resource requirements are substantial estimates call for several thousand logical qubits which translates to millions of physical qubits when accounting for error correction the widely cited gidney and ekera 2019 analysis estimated about 20 million noisy physical qubits running for 8 hours while gidney s 2025 update brought the estimate below 1 million physical qubits running for under a week the process requires around 10 10 10 10 1 0 10 gate operations current quantum computers face significant limitations ibm and google have systems in the 100 1 000 physical qubit range with improving fidelity and google demonstrated below threshold error correction with surface codes in 2024 however scaling to millions of error corrected physical qubits has not been demonstrated the gap between today s technology and the ability to break rsa 2048 is measured in decades not years however this threat is not immediate the development of post quantum cryptography standards nist fips 203 204 205 was finalized in 2024 specifically to prepare for this challenge post quantum cryptography response nist standardized three algorithms in 2024 fips 203 which uses ml kem formerly crystals kyber based on module lattices fips 204 which uses ml dsa formerly crystals dilithium also based on module lattices and fips 205 which uses slh dsa formerly sphincs based on hash functions these algorithms are believed to resist both classical and quantum attacks including those from shor s algorithm this security stems from the fact that they rely on mathematical problems that quantum fourier transform qft does not help solve shor s algorithm versus grover s algorithm these two algorithms represent different types of quantum speedup shor s algorithm provides exponential speedup applying to problems like factoring and discrete logarithms its cryptographic impact is severe as it breaks rsa ecc and dh conversely grover s algorithm provides only a quadratic speedup applicable to unstructured search problems which effectively halves the security level of symmetric keys while shor s algorithm is not compatible with current noisy intermediate scale quantum nisq devices because it is too deep grover s algorithm can be partially implemented for small search spaces neither algorithm is practically useful today summary shor s algorithm remains the prime example of exponential quantum advantage the process begins with the problem of factoring large integers a task that is classically intractable at cryptographic scales the quantum solution reduces factoring to period finding then uses qft to find that period exponentially faster since rsa ecc and diffie hellman all rely on the difficulty of factoring or discrete logarithms understanding shor s algorithm is essential for assessing the long term security implications of quantum computing the current response involves deploying post quantum cryptography standards such as ml kem and ml dsa however the timeline for a quantum computer capable of breaking current encryption remains years to decades away requiring millions of error corrected physical qubits written by dr donovan who writes on quantum computing research hardware and industry at quantum zeitgeist dr donovan ran his first quantum circuit on ibm s 5 qubit quantum experience in 2018 and has not put the subject down since he built quantumcomputingcourses com because the material out there forced a choice nobody should have to make pop science hand waving at one end phd level physics with no on ramp at the other and tutorial code that had usually stopped working by the time you found it he also writes on quantum computing at quantum zeitgeist quantumzeitgeist com was this tutorial helpful yes no share ready to go deeper browse structured courses from coursera edx udemy brilliant and more browse courses related tutorials continue learning with these guides bell inequalities and the chsh test how we know entanglement is real intermediate 30 min read read the bernstein vazirani algorithm implementing a hidden string finder in qiskit beginner 20 min read read rx ry and rz reaching any point on the bloch sphere intermediate 15 min read read previous quantum networking entanglement swapping and quantum repeaters next getting started with superstaq on this page 01 integer factorization 02 how factoring breaks rsa 03 factoring reduces to period finding 04 full shor s algorithm structure 05 modular exponentiation 06 factoring 15 a small example at a glance level intermediate read time 20 min read language python updated jun 2026 related tutorials bell inequalities and the chsh test how we know entanglement is real 30 min read the bernstein vazirani algorithm implementing a hidden string finder in qiskit 20 min read rx ry and rz reaching any point on the bloch sphere 15 min read courses on this quantum computing university of cambridge free advanced data structures rsa and quantum algorithms cu boulder paid quantum katas self paced quantum programming exercises microsoft free get one quantum email a week new tutorials courses worth taking and what changed in qiskit cirq pennylane this week no spam unsubscribe anytime email address subscribe 112 courses 220 tutorials 241 glossary terms 26 framework references 34 case studies quantumcomputing courses com free tutorials curated courses framework references and tools for anyone learning quantum computing written and maintained by dr donovan who writes on quantum computing research hardware and industry at quantum zeitgeist learn all courses free tutorials learning paths compare frameworks algorithm guide case studies quantum news reference glossary framework docs hardware guide qubit types history timeline cheatsheets bloch sphere quantum programming careers careers guide salary guide certifications interview questions jobs team training post a job talent pool about about this site editorial policy team faq events 2026 podcasts books contact as an amazon associate i earn from qualifying purchases 2026 hadamard llc quantumcomputingcourses com affiliate disclosure privacy terms cookies we use cookies to improve your experience and track affiliate performance see our cookie policy decline accept
|
