Shor's Algorithm is Scary NOW

Quantum computers are coming. When they arrive, which is probably sooner than you think, all of our classical encryption algorithms are dead.

Shor's algorithm was formulated by Peter Shor in 1994. By using some fairly simple number theory, a bit of computationally complex (for a classical computer) modular exponentiation and some quantum magic, Shor's algorithm can efficiently factorise numbers. The quantum magic is weird, very weird. By using the Quantum Fourier Transform a quantum computer can exploit the interference pattern generated in parallel universes to discover the periodicity of modular exponentiation without actually calculating successive powers. So what can we do when RSA dies and what should we do now? BB84 is provably secure and also relies on quantum mechanics, specifically the polarisation of light photons. I will demonstrate BB84 as well as some classical algorithms that we can be using now that are quantum safe. The talk includes an explanation of how Shor works, a demonstration of an implementation of Shor using Q#, an explanation of BB84 and classical quantum safe algorithms and a lot of fun in the process.