Cracking a Record Number

Mathematicians solve a three-century-old puzzle in 32 hours

Sandia National Laboratories in Albuquerque is a sprawling research establishment best known for its work on highly secret defense projects, including nuclear weaponry. Last week Sandia exploded a different sort of bombshell. Its mathematicians announced that they had factored a 69-digit number, the largest ever to be subjected to such numerical dissection. Their triumph is more than an intellectual exercise. It could have far-flung repercussions for national security. As anyone who has ever passed through intermediate algebra knows (or once knew), factoring means breaking a number into its smallest whole-number multiplicands greater than 1. For example, 3 and 5 are the only such factors of 15. But as numbers get larger, factoring them becomes increasingly difficult. Until recently, mathematicians despaired of factoring any number above 50 digits. They calculated that it would take the fastest computer, performing as many as a billion divisions a second, more than 100 million years to finish the task. Then, in the fall of 1982, a chance encounter closed the gap. During a scientific conference in Winnipeg, Canada, Gustavus Simmons, head of Sandia's applied-math department, was mulling the factoring problem over a few beers with another mathematician and an engineer from Cray Research, makers of the world's fastest computer. The engineer, Tony Warnock, pointed out that the internal workings of the Cray were especially suited to factoring, which is essentially done by a process of trial and error.

Unlike ordinary computers, the Cray can sample whole clusters of numbers simultaneously, like a sieve sifting through sand for coins. At Sandia, Simmons joined with his colleagues Mathematicians James Davis and Diane Holdridge to teach their own Cray how to factor. That involved developing an algorithm, or set of algebraic instructions, that would break the problem down into small steps. They succeeded admirably. In rapid succession they factored numbers of 58, 60, 63 and 67 digits. At this point, however, even the power of their Cray seemed to have reached its limit. But the Sandia team made one more try. This time their target was the last unfactored number in a famous list compiled by the 17th century French mathematician Marin Mersenne. The number:

132686104398972053177608575506090561429353935989033525802891469459697, which mercifully can be expressed as 2 ^251 --1. After a total of 32 hr. and 12 min. of computer time, snatched at odd hours over a period of a month, they came up with their answer.

Mersenne's number had three basic factors: 178230287214063289511 and 61676882198695257501367 and 12070396178249893039969681. Says Simmons: "You can't help feeling triumphant after solving a problem that has been around more than three centuries." Some may not share in the jubilation, especially if they are dependent on a widely used cryptographic system thought to be uncrackable. Known as RSA (the initials of its three inventors), it employs difficult-to-factor multidigit numbers to encode secrets and keep them secure. These include electronic funds transfers and military messages. By factoring the numbers, the codes can be broken. When RSA was first proposed, its inventors suggested using 80-digit numbers on the assumption that they were too big to be factored. Obviously, with researchers at Sandia closing in on ever larger numbers, even RSA could eventually fall to the code breakers.