Printer Friendly

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.
COPYRIGHT 1990 Science Service, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 1990, Gale Group. All rights reserved. Gale Group is a Thomson Corporation Company.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:mathematics
Publication:Science News
Date:Jun 23, 1990
Previous Article:Quasar light points to younger galaxies.
Next Article:Ancient skull spurs rift over hominid ties.

Related Articles
Primality tests: an infinity of exceptions.
Dubner's primes: searching for twin primes and other denizens of the number world.
Fermat proof flaw: fixing the details.
Last word not yet in on Fermat's conjecture.
Fermat's famous theorum: proved at last?
Prize offered for solving number conundrum.
Factoring reaches new heights.
Zeroing in on an infinite number of primes.
Owners of home computers join researchers in cracking problems and crunching data.
Prime pursuit: constructing an efficient prime number detector.

Terms of use | Copyright © 2016 Farlex, Inc. | Feedback | For webmasters