Major-league sieving for faster factoring.

Factoring a large number to determine its prime-number components typically takes a long time -- so much time on even the fastest available computers that an important method of encrypting digital information can count on the difficulty of factoring for maintaining security However, factoring techniques have improved sufficiently in recent years to bring numbers of more than 100 digits easily within range.

Last week, a team of researchers using a relatively new method known as the number field sieve succeeded in factoring a 116-digit number. This sets a record for the largest number yet factored by the general version of the technique.

More important, this factorization required less computer time than comparable 116-digit factorizations using a rival technique known as the quadratic sieve, says Arjen K. Lenstra of Bell Communications Research (Bellcore) in Morristown, N.J. Over the last few years, the quadratic sieve has been the favored technique for cracking large composite numbers (SN: 5/7/94, p.292).

Lenstra worked with Bruce Dodson of Lehigh University in Bethlehem, Pa., and Peter L. Montgomery of the Centrum voor Wiskunde en Informatica (CWI) in Amsterdam, the Netherlands, to set the new record.

Invented in 1988 by John M. Pollard of Reading, England, the number field sieve looked promising from the beginning, especially for factoring numbers of a special form. But it wasn't clear how practical and efficient the method would be for factoring large numbers in general.

In 1990, Lenstra and a colleague used the method to factor a 155-digit Fermat number, [2.sup.m] + 1, where m = [2.sup.9] (SN: 6/23/90, p.389). Meanwhile, mathematicians developed a version of the number field sieve that can be used for factoring any composite number.

Last month, researchers at Oregon State University in Corvallis, Reed College in Portland, Ore., and CWI used improved versions of the number field sieve to factor a 162-digit "special" number and a 105-digit "general" number.

Lenstra and his colleagues topped the 105-digit record. They required a month of computer time, using about 100 workstations at Lehigh for the initial steps and a MasPar MP-1 computer at Bellcore for the final stage, to complete the factorization.

Along the way, the researchers discovered a curious, unexpected speedup in certain steps. They can now take advantage of this behavior to achieve even faster factoring. "We've been working on it for years," Lenstra says. "Now it's becoming practical."