Grad Student Colloquium | Owen Sharpe | Primality Testing Is Easy but Factoring Is Hard

You've probably heard of RSA, and that it relies on factoring being a hard problem, but did you ever wonder where the large primes come from in the first place? We will take a tour through primality testing and factoring algorithms, starting with trial factoring and the sieve of Eratosthenes, through probabilistic methods like the Miller-Rabin probabilistic test and the Pollard rho method, to the bleeding edge of AKS and the quadratic sieve.

MC 5417