Monday, May 7, starting at 4:00 pm, Davis 301
Refreshments at 3:30 pm, Davis 2nd floor
These two topics are essential for public key cryptography: Factoring integers should be hard but recognizing primes easy. We survey the history of these topics and describe some of the fastest known algorithms for them. Some of these algorithms are rigorous and some rely on unproved hypotheses. Some are deterministic and some choose random numbers. Some are practical and some are theoretical. Your computer uses one of these algorithms every time you send a credit card over the Internet.