Fermat-number factors.

Fermat-number factors

Two computer scientists have reached an important milestone on the road toward factoring ever-larger composite numbers. Last week, Arjen K. Lenstra of Bellcore in Morristown, N.J., and Mark S. Manasse of the Digital Equipment Corp. Systems Research Center in Palo Alto, Calif., finished factoring the tenth Fermat number, proving that this 155-digit behemoth is the product of three prime numbers.

Fermat numbers have the form 2'"+1, where m = [2.sup.n] and n is zero or a positive whole number. More than three centuries ago, French mathematician Pierre de Fermat conjectured that all numbers of this form are prime -- that is, divisible evenly only by themselves and 1. His conjecture proved true for the first five Fermat numbers (ranging from n = 0 to n = 4). A century later, however, Leonhard Euler successfully factored the next Fermat number in the sequence. Since then, mathematicians have tried to factor larger Fermat numbers, reaching the eighth number (n = 7) in 1970 and the ninth (n = 8) in 1981.

To crack the tenth Fermat number (n = 9), Lenstra and Manasse used a recently invented method that significantly speeds the factoring of Fermat-type numbers. Various computers in a number of different locations provided essential information for the factorization, and the final step required a type of large computer known as the Connection Machine.

The computations show that the tenth Fermat number has a 49-digit and a 99-digit factor to go with the previously computed factor, 2,424,833. Both of the large factors start and end with the digit 7.

At the moment, reaching the next Fermat number appears out of the question. The number is so large that it easily overwhelms any known techniques for efficiently factoring large numbers.