Chapter 7: Fermat Primes

In 1650, Pierre de Fermat conjectured that any number of the form F(n) = 22n + 1 is prime, where n is a whole number {0, 1, 2, 3, …}. At the time, the formula was believed to work like this:

Input: nOutput: F(n)
021 + 1 = 3
122 + 1 = 5
224 +1 = 17
328 + 1 = 257
4216 + 1 = 65,537
5232 + 1 = 4,294,967,297
6264 + 1

Fermat proved that the formula always gave primes for n from 0 to 4, and the next number certainly seemed prime. He therefore conjectured that all the numbers in the sequence are prime, but he never wrote a complete proof. Today we call any number in the form 22n + 1 a Fermat number. A Fermat prime is a Fermat number that is prime.

Pierre de Fermat is the same Fermat known for Fermat’s Last Theorem, a conjecture that went unproven for 350 years.

The question of whether Fermat’s conjecture was correct was unresolved for nearly a century. In 1732, Euler proved Fermat’s conjecture false when he found that

F(5) = 4,294,967,297 = 641 • 6,700,417

While this calculation can now be done by a computer or graphing calculator in a fraction of a second, in Euler’s time all calculations had to be done by hand. So, instead of working through hundreds of calculations, Euler figured out what kinds of numbers were most likely to factor into 232 + 1. He found that only primes of the form p = 32k + 1 could divide evenly into 232 + 1. Working with this smaller set of possibilities, he tried each one until k = 20 (and p = 641) worked.

It took another 150 years to show that F(6), a 20-digit number equal to 264 + 1, was also not prime. As of May 2006, mathematicians have found the complete prime factorization of Fermat numbers up to n = 11, a 617-digit number with 5 factors (the smallest factor is 319,489). At least one factor has been found for over 200 Fermat numbers, going as high as F(2,478,782). Mathematicians now believe that the only Fermat primes are F(0) through F(4), but no one has proved this conjecture.

Cryptography is the process of coding and decoding information in order to keep it secret and secure.

Compare the difficulty of multiplying 641 by 6,700,417 and getting 232 + 1 to the difficulty of figuring out which two numbers multiply together to make 232 + 1. This relative difficulty is why factoring is more difficult than expansion, and is also at the heart of a popular version of cryptography called the RSA algorithm. To encrypt an RSA message, you need to know the product of two prime numbers. This product is public information. To decrypt the message, you need to know the two factors. The message is kept secure by the assumption that no one can easily figure out the two numbers by knowing their product.

In 1991, RSA announced their Factoring Challenge, posting large numbers and challenging mathematicians to factor them. They updated the challenge in 2001, offering cash prizes (from $10,000 to $200,000) to the first person or group factoring eight numbers between 174 and 617 digits long. By February, 2007, only the two smallest numbers (the 174-digit number, and a 193-digit number) have been factored. The remaining six were still unfactored, including this 212-digit number:

74,037,563,479,561,712,828,046,796,097,429,573,142,593,188,889,231,289,
084,936,232,638,972,765,034,028,266,276,891,996,419,625,117,843,995,894,
330,502,127,585,370,118,968,098,286,733,173,273,108,930,900,552,505,116,
877,063,299,072,396,380,786,710,086,096,962,537,934,650,563,796,359

Factor this number, and you’re in for a $30,000 payday.

The RSA algorithm is the basis for much of the security on the Internet. We still don’t know why factoring large numbers is inherently difficult—perhaps mathematicians just have not found the right technique. The RSA challenge is intended to encourage mathematicians to further their research in number theory to help prove that the RSA algorithm is secure.



Categories: Text

Tags:

%d bloggers like this: