How deeply does Real-World Cryptography cover Shor's algorithm?

Explains period finding and its cryptographic consequences, but stops short of implementation details or a formal proof.

Shor's algorithm

As explained in Real-World Cryptography

Shor's algorithm is a quantum algorithm that efficiently solves integer factorization and discrete logarithm problems.

Shor's algorithm is a quantum method for finding periods in mathematical functions. That capability efficiently solves integer factorization and discrete logarithms, the hard problems supporting much deployed public-key cryptography. section 14.1.3

Why cryptographers worry

For a function such as g^x mod N, finding a period can lead to efficient factorization. A sufficiently capable quantum computer could therefore break RSA, Diffie–Hellman, and elliptic-curve cryptography; merely increasing key sizes is described as impractical for RSA. section 14.1.3

The practical takeaway is:

Long-lived confidential data encrypted today with vulnerable public-key systems may become readable when capable quantum computers exist. section 14.1.3
Post-quantum cryptography seeks replacement asymmetric encryption, key exchange, and signature primitives rather than relying on larger traditional parameters. section 14.5

How Real-World Cryptography covers it

liveBook manning.com

Read Real-World Cryptography on liveBook Get the book at manning.com

Also explained in

liveBook manning.com

Quantum Programming in DepthShor's algorithm is a quantum algorithm for integer factorization with asymptotically better performance than the best known classical factorization algorithms.

Compare how 2 books explain 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.

This explainer was generated by Manning's knowledge graph from the text of Real-World Cryptography. The section links point to the parts of the book it draws on.