Reuter Honors Talk
Jack Reuter, Wes '16: Shor's Algorithm for Integer Factorization on a Quantum Computer
Abstract: Given an integer, return one of its prime factors. This problem is generally considered to be hard. There is no known factorization algorithm for a classical computer that uses a number of computational steps polynomial in the input size. Factoring is thus the basis of several modern cryptosystems, the most widely known and used being RSA. In 1994, however, Peter Shor proposed an algorithm for a hypothetical quantum computer that would solve the factoring problem in polynomial time. This talk explains how and why this algorithm works, emphasizing the number theory behind it, as well as the fundamentals of quantum computation. No mathematical background is assumed.