Primality testing is the act of checking whether a given number is prime or composite.
Basic testing
Intuitively the first idea one might have when considering whether a number is prime or not, is to use the definition of a prime number: a prime number n is an integer that has exactly 2 positive divisors, 1 and itself.
From this it follows that a simplistic primality test will just loop over all the integers less than the number and see if any divide it.
You can of course make this efficient by observing that you only need to go as far as sqrt(n). You can also skip all even numbers. No matter what you do, this method is slow, basically because you have lots of numbers to test (and that number increases rapidly as n increases).
Even without a full understanding of the problem it should be clear that this isn't the right way to go. Mathematics encourages laziness, only show what you have to. With this method you aren't just showing the primality of a number, you are also starting its prime decomposition.
Using Properties of primes
So how is one to test for primality? By using properties of prime numbers. For example, Fermat's little theorem states that if p is prime then for any integer a, ap = a (modulo p). We know that any prime number will pass the test. Lets see how other numbers fare.
Pick a number and run it through the test. Lets take p=25, a =2. If you do the calculation, you'll find that 225=7 (modulo 25). So far so good. Unfortunately there are some numbers which will slip through this particular test.
At first one might think that a=2 is a bad choice, or that by repeating the test with many values of a, we will have a good test. I've got some more bad news. There are numbers, known as Carmichael numbers that pass this test for every value of a. What more there are infinitely many such numbers.
There are many tests one can devise that will always let prime numbers through, but that will also let some composite numbers through.
Probabilistic tests
These build on the previous idea. Suppose you have a test with these properties
You can then use this simple test to make a better test, by passing a number through it k times.
How good is this new test , ie. if it says that a number is prime, how often is it wrong ? From the properties of the simple test it is 1/2k.
If k=100, then the probability of a composite number passing is about 1 in 1000000000000000000000000000000. This is pretty good, although there's still a chance you might get the wrong answer, it's a lot less likely than other causes for bad answers, like faulty components, large asteroids colliding with your computer etc. And if it really isn't good enough
for you, increase k by 1 and you divide the probability of being wrong by 2.
It's computationally cheap to get better and better results. If you're basic test is simple then you'll have a very fast algorithm that's almost always right. Maths packages such as Maple or Mathematica use this kind of test (Mathematica uses the Rabin-Miller test). These algorithms are fast and for real life purposes they are practically as good a non probabilistic test.
Depending on the test, there can be shortcuts. Suppose that the test can be run for a certain range of parameters, then for any given set of parameters then the set of composite numbers that past the test for all of these parameters has a smallest element. If that element is greater than the number you are looking at, then if it your number passes the test for this set of parameters you can be 100% sure that it is prime. Mathematica uses this kind of trick with the Rabin-Miller test.
Deterministic primality testing in polynomial time
This as good as it gets : deterministic means that unlike a probabilistic test it will never produce a wrong result. Polynomial time basically means that it is fast enough : run time is bounded by a polynomial function of the size of the input. This means that the time it takes to test a number doesn't grow too quickly and the test remains practical, even for large numbers. It has been believed for some time that primality testing was P-Class and people have searched for this elusive beast for many years.
On August 6th, 2002 Manindra Agrawal, Neeraj Kayal and Nitin Saxena of the Department of Computer Science & Engineering of the Indian Institute of Technology Kanpur posted an electronic preprint containing an algorithm that supposedly tests primality in polynomial time. The claim is that the algorithm runs in O(ln12n), possibly even in O(ln6n). The algorithm is surprisinly simple and takes just 13 lines of pseudocode. You can see the algorithm and their proof at
http://www.cse.iitk.ac.in/primality.pdf
sources: http://mathworld.wolfram.com/news/2002-08-07_primetest/
Eric W. Weisstein. "Rabin-Miller Strong Pseudoprime Test." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html