Team sieving cracks a huge number.

It's easy to multiply two large prime numbers to obtain a larger number as the answer. But the reverse process -- factoring a large number to determine its components -- presents a formidable challenge. The problem appears so hard that the difficulty of factoring underlies the so-called RSA method of encrypting digital information.

Last week, an international team of computer scientists, mathematicians, and other experts succeeded in finding the factors of a 129-digit number suggested 17 years ago as a test of the security of the RSA cryptographic scheme.

This feat and other work now complicate encoding schemes used for national and commercial security.

This effort required the use of more than 600 computers scattered throughout the world. Partial results were sent electronically to graduate student Derek Atkins at the Massachusetts Institute of Technology, who assembled and passed the calculations on to Arjen K. Lenstra of Bell Communications Research in Moristown, N.J. In the final step, which by itself consumed 45 hours of computer time, Lenstra used these data and a MasPar MP-1 computer with 16,000 processors to compute the factors.

"It was a nice piece of work -- a huge computation done over 8 months," says Burton S. Kaliski Jr. of RSA Data Security in Redwood City, Calif.

The magnitude of the effort required to factor a 129-digit number demonstrates the strength of the RSA cryptosystem, which typically involves numbers of 155 or more digits (SN: 9/7/91, p. 148). However, steady improvements in factoring methods are likely to force the use of significantly larger numbers in the future to ensure security. More worrisome are the consequences of new research apparently proving that under certain circumstances, factoring may actually be easy.

In 1977, when Ronald L. Rivest of MIT, Adi Shamir of the Weizmann Institute of Science in Rehovot, Israel, and Leonard M. Adleman of the University of Southern California in Los Angeles first proposed the RSA cryptosystem, even 50-digit numbers seemed beyond reach. As a challenge to computer scientists, the inventors used their scheme to encode a message, which could be decoded only if a certain 129-digit number could be broken down into its 64-digit and 65-digit factors.

At that time, Rivest predicted that factoring this number, using the fastest computers and best factoring methods then available, would require considerably more than 40 quadrillion years of computation. However, this prediction didn't take into account improvements in factoring methods. The existence of the RSA scheme prompted extensive work on factoring.

In 1981, Carl Pomerance of the University of Georgia in Athens invented a factoring method called the quadratic sieve. It proved faster than previous methods and lent itself to group efforts. Factoring could be broken down into lots of little tasks, with the resulting information then pieced together to factor the original number.

In 1988, Lenstra and a colleague coordinated an extensive, international effort using this method to factor a large number, successfully cracking a 100-digit behemoth (SN: 10/22/88, p.263). Last year, Paul Leyland, a computer system manager at the University of Oxford in England, Michael Graff of Iowa State University in Ames, and MIT's Atkins provided the software and assembled a team of volunteers to tackle the RSA number. Lenstra worked out the details of how to complete the factorization.

But this isn't the last word in factoring. In 1988, John M. Pollard of Reading, England, invented the "number field sieve" for factoring large numbers. Lenstra and his coworkers used the method in 1990 to factor a special, 155-digit number (SN: 6/23/90, p.389). New research reveals that the number field sieve may work significantly more efficiently than the quadratic sieve.

In a starting theoretical result that could call into question any cryptosystem based on factoring, Peter W. Shor of AT&T Bell Laboratories in Murray Hill, N.J., has just proved that factoring is "easy" when done on a special type of computer operating according to quantum mechanical principles. Although such a quantum computer does not yet exist, this finding has shaken the cryptographic community.