A curving path toward faster factoring.

The mathematical grapevine is buzzing with reports of a newly invented method for factoring large numbers. At the center of this excitement is a one-page summary sent out last month by Dutch mathematician Hendrik W. Lenstra Jr. of the University of Amsterdam. Lenstra's new factoring algorithm, in certain cases, may turn out to be faster than any of the general-purpose factoring methods now in use.

"It's a really beautiful idea," says Andrew M. Odlyzko of AT&T Bell Laboratories in Murray Hill, N.J., who was one of the first to hear to Lenstra's achievement. "Like most great ideas, it's extremely simple. For people with the right mathematical background, it takes literally two minutes to describe."

News of Lenstra's work has spread quickly. Several mathematicians are already writing computer programs to implement the method while others are tinkering with its steps or probing its implications.

"It's extremely straightforward to program," says Duncan A. Bell of Louisiana State University in Baton Rouge. Buell wrote his version of the Lenstra algorithm in the computer language C, requiring only about 250 lines for his program.

The key new feature in Lenstra's method is the use of ellipic curves: equations of the form y.sup.2 = x.sup.3 + ax + b, where values for a and b are chosen randomly. Lenstra started learning about these curves a year ago. Combined with his long-standing interest in primarily testing (determining whether a number is evenly divisible only by one and itself [SN: 3/6/82, p. 158]) and in factorization of integers (finding which prime numbers when multiplied together produce a given composite number), the result was a new factoring algorithm.

"There was an element of coincidence in the convergence of these ideas," says Odlyzko. "Things somehow came together and clicked."

Lenstra's method works best when the number to be factored turns out to be the product of three or more prime numbers or the product of two primes that are far apart in value. This makes Lenstra's method attractive for factoring numbers drawn from a table of "most-wanted factorizations"--a list of particularly difficult numbers to factor (SN: 1/14/84, p. 20). These numbers come up in number theory and other types of mathematics research.

"If two factors differ greatly in size, then Lenstra's new algorithm can buy a great improvement in running time," says Gustavus J. Simmons of the Sandia National Laboratories in Albuquerque, N.M. Simmons heads the Sandia group that presently holds the record for factoring the longest "hard" number -- 71 decimal digits--using a general-purpose factoring method (SN: 3/17/84, p. 171).

How big the improvement will be depends on how well Lenstra's algorithm runs when it is written out for a computer. "You have to test these things," says Hugh C. Williams of the University of Manitoba in Winnipeg. "It's one thing to say theoretically what it should do and quite another matter to discover, when you put it on a machine, just how fast it actually goes. But it deserves to be looked at."

So far, Lenstra's algorithm doesn't threaten the security of cryptosystems that depend on the difficulty of factoring numbers. These schemes often involve the product of two primes, but the primes can be chosen so that they are relatively close together in value (SN: 11/24/84, p. 330). For factoring such composite numbers, Lenstra's algorithm appears to be no netter than the "quadratic sieve" method, invented by Carl Pomerance of the University of Georgia in Athens and currently the fastest general-purpose factoring method.

"But it's a brand new idea," says Pomerance. "Maybe we'll find some variation of it that will make it competitive with the things that we have now or even make it much better." He adds, "With new algorithms coming along, it's hard to count on the security of cryptosystems. Who's to say that someone can't come up with a new idea that's going to work fantastically?"