Rich’s Collection of Geekery

Thank goodness for the Internet… we covered this topic in cryptography class (and it was explained quite well), but this web page seems to spell it out equally well in plain English:

This method is based on Fermat´s little theorem. It is well known that for any prime number you choose, p, and any other number, a,

a^(p-1) = 1 (mod p) Which means that, a^(p-1) - 1 = 0 (mod p) i.e. p divides the left hand side, or: p is a factor of the left hand side. FACTOR! That´s what we want to hear!

So all we have to do is try out the converse. Assume that the number you wish to factor, N, has some unknown prime factor, p. We just try a bunch of a^k - 1 numbers and see if it they have a common factor with N. If so, we found our p. Done!

A useful application of this theory is in breaking public key ciphers like the RSA algorithm. In my class we had a project where we really put it to use — that was a lot of fun!