Home » Reading clubs » Classic » Summary: Shor (1999) Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Summary: Shor (1999) Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

[Summary by Søren Riis]

On the morning of Wednesday 18th of May, a reduced select group met to discuss “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” P. W. Shor [1].

Finding the factors of a given large number is a fundamental problem in computing called factoring. Shor’s result is that factoring can be solved in roughly n^2 steps on a quantum computer (where n is the number of bits in the number we want to factor). In contrast, factoring requires exponentially many steps on an ordinary computer. A traditional computer is based on bits. Each bit can either be zero or one. A quantum computer instead uses q-bits. A q-bit can either take value zero, one or some superposition of zero and one.The way Shor’s algorithm works is that it first converts the problem of factoring into the problem of finding the period of a really long sequence. It is this issue that is the central quantum mechanical part of Shor’s algorithm. Once the period is found, the result can then be used to factorise the number.

Public key cryptography, i.e. the RSA algorithm we discussed in a previous meeting, relies on the assumption that factoring is computationally hard. RSA would be rendered insecure if Shor’s quantum factoring algorithm could be implemented.
After the meeting, I had some fun writing a simple python program on my laptop that can simulate Shor’s algorithm. Maybe at a later stage this program could be turned into a proper teaching tool


[1] P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM Rev., vol. 41, no. 2, pp. 303–332, Jan. 1999.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: