Quantum Computing and Shor's Algorithm (part 2)

The Universal Turing Machine described by Alan Turing in the mid 1930s
created a perspective by which we judge computational complexity,
decidability, and other foundational topics.  However, with the current
understanding of quantum mechanics, we know of some tasks which are
performed in the natural world and which cannot be simulated by a Turing
Machine.  Quantum computing is a method by which these processes can be
reproduced.

Despite this intellectual curiosity, the utility of quantum computing
was not demonstrated until Peter Shor developed an algorithm for
factoring large numbers in 1994.  Not only does this algorithm operate
in efficient time on a quantum computer, but it also impacts the area of
secure-key cryptography.

In the second part of this talk, we will discuss the problem of 
factoring large numbers into their primes, attempt to show how it 
reduces to the period-finding problem, and show how Shor used the
power of the quantum computer to solve this problem in polynomial
time, given sufficient quantum resources.