Are there quick ways to point out that certain numbers are primes? I would like to know if there are any methods to prove that a given number is prime. I know that for a number in general the problem is very complicated, but perhaps for numbers of a given form, or for some numbers that verify certain conditions, you can prove that the number is prime with relative simplicity. For example, some algorithm to reduce the number of divisors you have to check.
Do such methods exist? If so, do you know any examples?
 A: Pratt proved that each prime has a polynomial-sized proof of primality (now called a Pratt certificate).
Pomerance shows that more is true: each prime has a proof requiring only about (2.5 times the prime's length in binary) multiplications mod the prime itself.
Of course for special classes of primes, like Mersenne (Lucas-Lehmer test) and Fermat primes (Pépin's test), short proofs have been known for a long time.
Guy, Lacampagne, & Selfridge give a different method of very short proofs of primality. It's a bit more intuitive, and perhaps more appropriate for your intended audience, but it probably applies only to a finite set of primes. Agoh, Erdős, & Granville fix the finiteness problem, but at the cost of a longer expression; you can decide which works better for you.


*

*V. Pratt, Every Prime Has a Succinct Certificate (1975).

*Carl Pomerance, Very short primality proofs (1987)

*R. K. Guy, C. B. Lacampagne, and J. L. Selfridge, Primes at a Glance (1987)

*A. Granville, T. Agoh, and P. Erdős, Primes at a (somewhat lengthy) glance (1997)

A: If a number is under $2^{64}$, we know the BPSW test is adequate -- it has no counterexamples under that.  Hence we can treat it as a proof.  We also have deterministic sets of Miller-Rabin bases for under $2^{64}$ and in September of this year a paper showed deterministic bases to approximately $3.317 \times 10^{24}$.
The methods from BLS75 rely on partial factoring.  This includes earlier methods like Pocklington.  There are a lot of numbers where finding enough small factors of $n-1$ or $n+$ is easy.  These give deterministic proofs with little effort.  I find this works extremely well for most numbers up to 80 bits, and theorem 5 works surprisingly well out to 40-50 digits.  It's vastly better than trying to do trial division.
You can extend that to ECPP, though it isn't as obvious as "n-1 has small factors".  There are some numbers where finding each step in the chain is very easy.  This isn't terribly practical just because it's not really obvious which numbers these are.
The Lucas-Lehmer test allows fast proofs of Mersenne numbers ($2^p-1$).
Proth's theorem allows very fast proofs for numbers of the form $k \times 2^n+1$ ($k$ odd, $k < 2^n$).
Lucas-Lehmer-Riesel allows fast proof for numbers of the form $k \times 2^n-1$ ($k < 2^n$).
There are some extensions to LLR, e.g. for numbers of the form $k \times b^n \pm h$ though they're not as easy to implement.  For instance, Perl/ntheory implements $k\times 2^n \pm 1$, while Penné's LLR implements $k\times b^n \pm 1$.
Addendum: it isn't entirely clear, but it's possible that you may think trial division is the method normally used for primality proving.  It is used for very small number (say under a million) but it's slower than other methods before long, as has horrible growth.  We have much better methods.  Typically we can just use deterministic M-R or BPSW for small inputs (e.g. under 64 bits).  APR-CL and ECPP are commonly used for general forms above that, and they will prove arbitrary 250 digit primes in a bit under a second on a single core of a modern CPU.  700 digits in under a minute.  These sizes are, of course, wildly unfeasible with trial division.  ECPP for general forms is up to a record of 30k digits, albeit with a lot of computation.  Proving arbitrary primes up to a few thousand digits is quite straightforward for most computers with tools like Pari/GP or Primo.
