We'll present and prove the Rabin-Miller test, a randomized algorithm that correctly decides whether a number is prime with high probability (and in poly time). The key to the Rabin-Miller test, along with earlier probabilistic algorithms, begins with Fermat's Little Theorem. Although Fermat's Little Theorem holds for primes, it fails for most other numbers, except for a class of numbers named Carmichael. We'll prove Rabin-Miller works both in the easy case, as well as for these "prime imposters."
All the group theory we need will be covered in the presentation.