Shor's algorithm
Shor's algorithm is a quantum algorithm that efficiently factors integers and solves discrete logarithms using quantum period finding.
Quantum Programming in Depth
Shor's algorithm is a quantum algorithm for integer factorization with asymptotically better performance than the best known classical factorization algorithms.
- How it is used
- Frames integer factorization as a candidate application for quantum advantage when the problem has exploitable structure.
- How deep it goes
- Explains the factorization goal, periodicity, asymptotic promise, and practical caveat without deriving the algorithm or implementation.
- Examples
- Uses factoring a single number and finding its divisors as the concrete problem example.
- What you can do after
- Evaluate whether factorization has the structure and scaling needed to justify a quantum approach.
Read how Quantum Programming in Depth explains Shor's algorithm →
Real-World Cryptography
Shor's algorithm is a quantum algorithm that efficiently solves integer factorization and discrete logarithm problems.
- How it is used
- Frames the quantum threat to asymmetric cryptography and motivates migration toward post-quantum cryptography.
- How deep it goes
- Explains period finding and its cryptographic consequences, but stops short of implementation details or a formal proof.
- Examples
- Uses g^x mod N, RSA, Diffie–Hellman, elliptic curves, and long-term health or government records as threat examples.
- What you can do after
- Evaluate which public-key systems are vulnerable to future quantum attacks and why post-quantum migration matters.
Read how Real-World Cryptography explains Shor's algorithm →
Related concepts
- factorizationaddresses · Factorization is the decomposition of a mathematical object, such as an integer or joint distribution, into simpler multiplicative factors.
- discrete logarithmaddresses · A discrete logarithm is an exponent or scalar that relates a specified group element to a base or generator under the group operation.
- periodaddresses · A period is the interval or number of steps between successive repetitions of a function, process, sequence, pattern, or state.
- quantum algorithmkind of · A quantum algorithm is a computational procedure designed to run on a quantum computer and exploit quantum-mechanical states or operations.
- post-quantum cryptographycontrasts with · Post-quantum cryptography is cryptography designed to resist attacks by quantum computers while generally running on conventional computers.
- RSAcontrasts with · RSA is a public-key cryptosystem based on the computational difficulty of factoring large composite integers and supporting encryption and digital signatures.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.