Fermat Number Factorizations

Fermat once conjectured that all numbers of the form 2^(2^n) + 1 were prime. More or less this was based on the fact that the first few such numbers 3, 5, 17, 257, 65537 were all prime. This was the farthest out that the primality of such numbers could be tested in Fermats day since the very next number in the sequence is 4294967297 which rather understandably Fermat did not recognize as being 641*6700417.

So far as we know the only prime Fermat numbers are in fact the first few numbers known to Fermat to be prime. Primality testing of the Fermat numbers and more challengingly the factorization of Fermat numbers has become something of a past time in number theory especially since computers got into the fray.

I should take a moment to talk about just how large the Fermat numbers really are. It is convenient to think of fermat numbers as binary strings. The Fermat numbers in binary are 11, 1001, 10000001, 1000000000000001, 100000000000000000000000000000001, .... and so on. The formula for producing them being to make a string of 2^n zeroes and then replacing the first and last zero with 1's. Viola a binary expansion of the n'th Fermat number. Rather obviously these numbers grow very very large very very quickly. Because of the difficulty of factorization of large numbers and the phenomenal growth of these numbers we have managed to completely factor only the first 11 Fermat numbers. This may not seem like much of an accomplishment but consider that "unbreakable" RSA cryptography uses numbers of a few hundred digits. F11 has 2048 binary digits which translates to over 600 decimal digits. One should keep in mind of course that RSA uses numbers which are worst case for factorization algorithms so factoring a 600 digit RSA number would be much harder than factoring a 600 digit Fermat number.

F12 is a 4096 digit number in binary (1234 decimal digits) and so even after dividing out all the known factors 114689, 26017793, 63766529, 190274191361, and 1256132134125569 we are still left with the incredible task of factoring a number of over 1200(decimal) digits. Although finding these gargantuan factors for F12 is certainly a laudable feat we have barely scratched the surface of the problem.