Kyle Box with Prof. Harsh Mathur Title

A Quantum Algorithm for Testing for Mersenne Primes

In this project we will be looking for a quantum algorithm to solve a specific number theory problem – testing for Mersenne primes. Prime numbers play an important role in modern life, mostly in various data encryption schemes, and Mersenne primes are particularly interesting. There is currently only one quantum algorithm known to be better than its classical counterpart for an important problem. Shor’s algorithm is a quantum algorithm for factoring an integer in O((log N)^3) time, while no classical algorithms can run in time that is polynomial in log N. We will attempt to find an algorithm to test if a number is a Mersenne prime which will run faster than classical algorithms.