Motivation: generating prime numbers
Almost all of modern cryptography involves large prime numbers: RSA, ElGamal, DSA, even some Ellipticcurve cryptosystems. The problem of generating large primes suitable for use in cryptography is unfortunately often one passed over by introductory material on the subject.
Prime numbers are often generated by the use of primality tests: given a number, they produce a judgement as to if the number is prime or composite. Surprisingly enough, the process of generating a large random odd number and checking its primality is enough: using the Euler Criterion, the number of primes until a certain number is approximately . So (as an example) the number of primes representable by a 128bit integer is about: When compared to the amount of values a 128bit integer, roughly , this implies that a random 128bit integer has about a 1% chance of being prime. If the primality test is fast, then this is clearly a very feasible way to generate primes. ^{1}
So, let's talk about one algorithm: the Fermat primality test.
The Fermat primality test
The idea behind the socalled Fermat primality test is extremely simple, and uses a theorem that gives the test its name:
Fermat's Little Theorem
Let be a prime, and an integer such that . Then .
The actual algorithm itself: given a positive integer number , pick a random integer such that , and then calculate . Clearly, if , then the number is not a prime, by the contrapositive of Fermat's Little Theorem.
Or, more formally:
Fermat Primality Test
Input: Positive integer .
Output: "Composite" or "Prime".
 Pick at random.
 Compute .
 If then return "Composite".
 Compute .
 If then return "Prime".
 Otherwise return "Composite".
The GCD calculation is in place just in case the random number picked is actually a factor of . The chances of this occuring are low enough that it may seem fruitless, but it will be useful to refer to later on.
Examples
Here's an example: let (which is prime), and pick . Then note that , which is a simple verification of Fermat's Little Theorem.
For a more interesting example, try . Since , clearly the test should fail. Pick and then we see that . But if we choose , it is also interesting to note that  which appears to verify that 129 is prime, even though we know it is not!
This leads to an important fact about the Fermat primality test: it sometimes lies! It is important to note, however, that it never lies about a number not being prime. If the Fermat test claims a number is not prime, it definitely is not. However, if it says it might be prime, then it is entirely possible that it is lying.
At first, this seems a deathblow to the Fermat test. A test that doesn't always work seems to be not a very useful test. But a ray of hope remains: what if it lies only with an extremely low probability?
Probability of lying
We seem to have a bit of a difficulty now. How can we determine if the Fermat test lies for a given input? Well, here's a place to start. How about we define the list of composite numbers for which a given results in a Fermat lie?
Fermat liars
A number is a Fermat liar for a composite number iff . The set of Fermat liars for a composite positive integer is the set .
This gives us something to think about: the chance for the Fermat test to lie is related to the size of the set . If is small, the chances of lying are small, and the same goes viceversa. But how small?
That's the question, really. Here's something to consider: remember that GCD test in the psuedocode for the Fermat test above? If we discard everything that has GCD that is not one, then, well . . . we get that , don't we?
Let's try something, then. Using and again from before, . So . Perhaps elements of the multiplicative group? But with , the same thing happens; the GCD is 1.
But this leads to an interesting fact: we only care about elements of . Anything outside will be discarded by the GCD test. But now since by construction, we really note that .
Here's a theorem to get you thinking:
Lagrange's Theorem
Let be a group, and a subgroup of . Then .^{2}
Can we form a subgroup out of ? Let's try it, shall we? Using from before, note that is such that , meaning that . But we see that , and . (Since , it is clearly invertible and hence . So it seems that may be a subgroup, from a trivial verification example.
The subgroup test in abstract algebra states that a set is a subgroup of a group iff
 , where is the identity element of .
 For , .
 For , .
Well, clearly , and so we can knock off the first condition. The second gives a little more trouble, but soon falls as soon as we notice that if and , then , as is a commutative group. So , and the second condition applies.
The third condition requires a touch more thought, but is solved just as easily as one finds that
So we see that is indeed a subgroup of ! This is a very interesting result: with a little bit of finesse, we can actually get a fairly decent estimate of the probability of lying here.
For the moment, just assume that . So there is an element in that is , since by Lagrange's Theorem we see that , we can conclude that at the very most, the probability of lying is .
The deathblow to the Fermat test still seems intact, until we consider the possibility of running the Fermat test multiple times. Theoretically, if we were to choose the integer at random, then each test would be independent. If we use basic probability theory, and consider executing the test times (say ), the chance of all tests lying (and hence the chance of having a composite number) is of course . For , that's approximately  a probability so small as to be essentially zero.
But, you may say, this is all relying on the fact that ! Are there numbers for which this is the case?
Introducing: Carmichael numbers
Sadly, the answer is yes, and these numbers are known as the Carmichael numbers, named after a fellow by the name of Robert Carmichael. Even worse news: there are an infinite number of Carmichael numbers, so we can't just store a list of known Carmichaels and avoid them. They are, fortunately, extremely sparse ^{3} and hence really are not that much of a problem.
So, what is a Carmichael number, exactly?
Carmichael numbers
A Carmichael number is a positive integer that satisfies:
 is composite,
 is squarefree,
 For all primes , .
Here's a quick sketch of a proof of why Carmichael numbers defeat the Fermat primality test, for completeness' sake:
Proof:
Let be a Carmichael number. Then because is composite, we know that for some primes and some positive integers , In particular, because is squarefree, , we see that
Let be arbitrary. Then decompose into values as follows: Because , we know that (group closure), and thus that . Hence there is no .
So now, because , we can use the Chinese Remainder Theorem to state that there is some unique number such that . But satisfies this: because , and hence (where ) by Fermat's Little Theorem.
So we may conclude that , and hence the arbitrarilychosen number is a Fermat liar for (because ), as required.
So: yes, we do have to worry about Carmichael numbers with the Fermat test, but not really to any significant degree. As noted before, their occurence is low enough that for all but the most paranoid of situations, the Fermat test is really quite sufficient.
Conclusion
So: the Fermat primality test is certainly a simple algorithm with some very interesting properties. It performs well enough in most situations, and also has the advantage of being extremely quick. I'm not suggesting that the next time you need a prime number, you should implement the Fermat test  there are plenty of good libraries out there that will do this for you  but it seems like a good idea to at least be aware of the general process.
Happy hacking,
 ethereal

One may ask the question 'What happens at larger bitsizes?' The chance is actually ; hence the chance scales about inverselinearly with the number of bits. ↩

There are many equivalent ways of stating Lagrange's Theorem. This just happens to be the most convinient for this context. ↩

They seem to appear roughly one every fifty billion numbers. There is a list of the known Carmichael numbers up to , for the curious. ↩