If we wish to know that a number is prime we may try seeing if passes many primality tests (easy but non-rigorous) or we may attempt to factor the number completely (rigorous but onerous). The middle ground that we will discuss consists of specially designed methods that prove a number is prime with less work than attempted factorization.