In the introduction part of "Rational Points on Elliptic Curves", it was mentioned that there are very quick ways to check that an integer is itself a prime although it is virtually impossible to perform a factorization. And I'm curious how to quickly determine whether a large number is prime.
Primality is a much easier problem than factorization in practice, and the best known complexity results are better as well.
As rywit mentioned, the Wikipedia page has lots of good information.
From a practical point of view, this graph gives an examples of times for single threaded implementations of a few primality proof methods on a 4770K, as well as BPSW, a fast probable prime test. It doesn't cross 1 second for average time to prove primality on random primes until ~250 digits using either APR-CL or ECPP. BPSW is still under 0.2 seconds at 2000 digits, albeit a probable prime test. The time for BPSW is 2.5-3x the cost of a single Miller-Rabin test.
Easiest way to test: use Pari/GP and its
ispseudoprime function for probable prime test (using AES BPSW) or
isprime function for an APR-CL proof. Other useful software includes OpenPFGW, Primo, ecpp-dj, mpz_aprcl, Wolfram Alpha, and others.
- various methods for special forms (e.g. Mersenne, Proth, 2^n +/- 1, etc.). Some software with at least one of these include OpenPFGW, prime95, LLR, Perl/ntheory, and more.
- ECPP. The fastest method in common use for large inputs. Primo is the standard, especially for >2k digits. There are a couple others you can find, including my ecpp-dj open source software. These give certificates of primality, which is a big advantage over other methods. This means anyone can independently and quickly verify that it passes all the necessary tests.
- APR-CL. Pari/GP, mpz_aprcl, and alpertron are some implementations.
- BLS75 methods. From the seminal 1975 paper, this shows numerous ways to prove primality based on partial factoring. Pocklington's test from 1914 is a simple form of this type of test.
- AKS. Landmark theoretical result. Quite slow in practice, so isn't normally used. IMO the probability of a programming error in an AKS implementation is higher than the chances a composite will pass a well designed and implemented probable prime test.
- Trial division. Doesn't scale.
- Probable prime tests, such as BPSW and running random-base Miller-Rabin tests. These aren't proofs, but done well they're good enough for almost all purposes, and they're very fast. Most proof code starts with a probable prime test of some sort so it can quickly give an answer for almost every composite input.