How to determine whether a large number is prime 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. 
 A: 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.
Algorithms include:


*

*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.

