Chapter 12. Shor’s Factoring Algorithm

If you’d heard about one application of quantum computing before you picked up this book, there’s a good chance it was Shor’s factoring algorithm.

Quantum computing was mostly considered to be of academic, rather than practical, interest until Peter Shor’s 1994 discovery that a sufficiently powerful quantum computer can find the prime factors of a number exponentially faster than any conventional machine. In this chapter, we take a hands-on look at one specific implementation of Shor’s QPU factoring algorithm.

Far from being a mere mathematical curiosity, the ability to quickly factorize large numbers can help break the Rivest–Shamir–Adleman (RSA) public-key cryptosystem. Anytime you spin up an ssh session you’re making use of RSA. Public-key cryptosystems like RSA work by a process wherein a freely available public key can be used by anybody to encrypt information. But once encrypted, the information can only be decrypted using a secret, privately held key. Public-key cryptosystems are often compared to an electronic version of a mailbox. Imagine a locked box with a slit allowing anyone to post (but not retrieve) a message, and a door with a lock to which only the owner has the key. It turns out that the task of finding the prime factors of a large number N works really well as part of a public-key cryptosystem. The assurance that someone can only use the public key to encrypt and not to decrypt information rests on the assumption that finding ...

Get Programming Quantum Computers now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.