The hunt crossed three continents and required hundreds of computers, but a team of researchers captured a prize few thought possible _ the prime factors of the 100-digit number on mathematicians' ``most wanted'' list. The breakthrough could have important implications for governments and banks, which use large-digit numbers in security systems on the assumption they provide a code too difficult to break. But the pleasure of the hunt concerned researchers more. ``Why did we go after it?'' University of Chicago computer scientist Arjen Lenstra said Wednesday. ``Because people compile lists.'' The number, which begins 9,412,343,607 ... and stretches on for 90 more digits, defied all previous efforts to find its prime factors. The factors of a number are two numbers that, when multiplied together, yield the larger number. A prime number is one that is evenly divisible only by 1 or itself. The prime factors of 21, for example, are 3 and 7. By comparison, the prime numbers that solved the 100-digit number are, respectively, 41 digits and 60 digits long. Finding the prime factors of such large numbers was thought to be so difficult, in fact, that many security systems assume such computations to be beyond the range of even the most powerful computers being applied for long periods of time. Governments transfer secret messages and banks transfer funds electronically by encoding the information in large-digit numbers that require the receiver to know its prime factors in order to decipher the information. ``Ten years ago, everybody suggested 80 digits were safe. Nowadays, that's trivial'' said Lenstra, co-director of the project with Dr. Mark Manasse of the Digital Equipment Corp.'s Systems Research Center in Palo Alto, Calif. ``I think 150 is reasonable,'' he continued. ``But personally, I'd go a little beyond 200 now.'' Computer scientists had theorized that a single computer doing a million calculations per second would have needed 25 years to solve the problem. Even a state-of-the-art supercomputer such as the Cray would need about 10 months of constant computing _ that at a cost of thousands of dollars per hour. Lenstra and Manasse, however, factored the number in just 26 days. They began their attack on the 100-digit number by breaking the problem into smaller tasks, then farmed them out to about 400 computers in the United States, Europe and Australia through an exisiting electronic mail network. All the computers used in the project worked on the factoring problem only when they were not being used for anything else. Each time a problem was solved, it was relayed by electronic mail to Digital's Palo Alto lab. The last sequence of numbers required to solve the entire problem flashed across a computer screen at 2:03 a.m. PDT Tuesday. ``One of the really nice things about this effort is that it cost us virtually nothing,'' Lenstra said. ``We contacted friends, other computer scientists, anybody that thought factoring was fun and got them to participate.'' Lenstra, 32, a visiting professor in Chicago's computer science department is unsure where the next horizon lies. He said every time the length of the number goes up by three digits, the time needed to compute the prime factors doubles. ``But we don't know what our problem-solving limit is until we find out how much interest is out there and how big an electronic mail network we can assemble. ``We've already started on a 102-digit number,'' he concluded, ``just to keep us busy.''
