Primality testing is actually much easier than integer factorization thanks to Fermat's "little" theorem. Methods based on this theorem, including the Lucas-Lehmer test for Mersenne primes, can identify prime numbers on classical computers in polynomial time. However, factorization is not possible with this method.