AP NEWS
Related topics

Scientists Crack Fierce Math Problem

October 12, 1988

NEW YORK (AP) _ Mathematicians working with hundreds of computers on three continents have successfully split a record-long 100-digit number into two prime factors, according to a report published today.

The final numerical sequence required for the solution flashed into a laboratory in Palo Alto, Calif., at 2:03 a.m. PDT Tuesday, marking a development that will probably force cryptographers to rethink how some codes used by governments and banks are applied in the future, said The New York Times.

The 100-digit number was chosen by an elaborate mathematical screening process to afford the maximum possible difficulty, the Times said. The two factors found are 41 digits and 60 digits, respectively.

A number’s factors are smaller numbers that when multiplied by each other produce the larger number. A prime number is one that is evenly divisible only by one or by itself.

The project was organized by Mark S. Manasse, of the Digital Equipment Corp.’s Systems Research Center in Palo Alto, and Arjen K. Lenstra of the University of Chicago. They were helped by 12 users of about 400 computers in the United States, the Netherlands and Australia who donated computer time when not needed for their regular work.

Factoring the 100-digit number took less than a month. In theory, one expert said, a supercomputer like the Cray, operating continuously, could have solved the problem in about a week. But supercomputers cost thousands of dollars an hour to run, and operating the range of simpler computers for short periods when they were idle kept the cost down to virtually nothing, the Times said.

There has been rapid progress in the factoring field this year, with the same group establishing a record with a 96-digit number just three weeks ago. According to Lenstra, the record has been broken about once a year this decade. Manasse predicted a 106-digit number will have been factored by the end of the winter.

Here is the problem they solved:

The number to be factored: 9,412,343,607,359,262,946,971,172,136,294,514, 357,528,981,378,983,082,541,347,532,211,942,640,121,301,590,698,634, 089,611, 468,911,681.

The factors found: 86,759,222,313,428,390,812,218,077,095,850,708,048,977 X 108,488,104,853,637,470,612,961,399,842,972,948,409,834,611,525,790, 577,216, 753.

AP RADIO
Update hourly