Conference rusure::math

19.0. "Advances in factoring" by HARE::STAN () Tue Jan 31 1984 03:23

From:	ROLL::USENET       "USENET Newsgroup Distributor" 30-JAN-1984 22:09
To:	HARE::STAN
Subj:	USENET net.math newsgroup articles

Newsgroups: net.crypt,net.math
Path: decwrl!decvax!harpo!ulysses!mhuxl!ihnp4!ihuxx!ignatz
Subject: Re: Arnold Arnold
Posted: Mon Jan 23 17:44:08 1984


It might be even worse:  From the Jan. 14th, 1984 issue of Science News:

Science News of the week
Faster Factoring for Cracking Computer Security

For years, mathematicians have known that the number (11^64)+1 is
really the product of at least two smaller numbers multiplied
together, but this 67-digit number until recently withstood their
repeated attempts at finding its factors.  Last month,
mathematicians at Sandia National Laboratories in Albuquerque,
N.M., made it the longest "hard" number ever to be factored by a
general-purpose factoring routine.  That record is likely to fall
within the next few weeks when the Sandia group, using their
specially designed method for factoring on a Cray computer,
expects to crack a 71-digit number.  Only eight years ago, the
best anyone could do, using a day of computer time, was to factor
a difficult 40-digit number.

While factoring was once the pursuit of a few eccentric
mathematicians, it has now become an important activity for
people concerned about computer security (SN: 7/3/82, p.12).
Several important cryptographic methods (SN: 9/26/81, p. 205)
depend on the inherent difficulty in factoring compared with
finding out whether a number is prime (divisible only by itself
or one)(SN: 3/6/82,p. 158).  The recent rapid advances in
factoring larger and larger numbers are making some computers
vulnerable that just a year ago were thought to be adequately
protected by cryptographic systems.

Sandia's Gustavus J. Simmons says, "Factoring is one of a whole
class of problems that are so difficult that they're at the edge
of computational feasibility.  You quickly get to numbers that
you can't factor."  However, during the last year os so,
mathematicians have begun to take advantage of the way particular
computers handle information internally by matching a
mathematical scheme or algorithm for solving a problem to the way
the machine operates most efficiently.

At Sandia, James A. Davis and Diane B. Holdridge started with a
method for factoring called the "quadratic sieve,", originally
invented by Carl Pomerance of the University of Georgia in
Athens.  This method breaks the problem of factoring a big number
into an enormous number of smaller problems, each of which
provides some information about the original factorization.  The
answers go into large arrays in the computer's memory.  The
"sieving" operation requires selecting and manipulating entries
at locations that are all the same distance apart.  The Cray is
designed to do just that.  It can hop directly from one regularly
spaced array position to another instead of counting off every
location along the way.  Matching the Pomerance algorithm to the
Cray's "architecture" cut the time to factor a 55-digit number
from more than 50 hours to less than four hours.

Then, Davis improved the factoring algorithm by finding a way to
make the sieving operation more efficient.  After this change, a
58-digit number that had required 8.8 hours took only 1.8 hours
to factor.  The Sandia researchers reached a new limit when they
tried a 67-digit number.  The million words of high-speed memory
within the Cray simply wasn't big enough to hold all the
necessary numbers.  Holdridge had to steal "bits" from the
computer's operating system to fit the computation within the
computer.  Now, the Sandia group is switching to a larger model
of the Cray computer that will allow them to factor even bigger
numbers.

To put their factoring method through the toughest possible
tests, the Sandia group has been working on numbers of special
interest to mathematicians, including those numbers on a "10
most-wanted" list of candidates for factoring.  Six numbers from
that list have already been done at Sandia.  Their current target
is (10^71)-1.  Although that number is divisible by 9, division
leaves a string of 71 ones.  This "hard part" is known to be
factorable, but no one has yet found its factors.

Other groups are also attacking the problem of factoring large
numbers.  For instance, Samuel Wagstaff at Purdue University in
Lafayette, Ind., and Jeffrey Smith and Carl Pomerance at the
University of Georgia are building a computer specially designed
just to factor numbers.   When the machine is ready, they expect
to be able to factor a 78-digit number in a day.  The consensus
at a recent meeting of mathematicians interested in factoring was
that it may be possible to factor any 100-digit number by the
1990s.

Simmons says, "Computational feasibility is something that
changes all the time."  Given Sandia's dependence on
cryptographic systems, some of which apply the difficulty of
factoring large numbers, for protecting information such as
weapons systems data, Simmons says,"It's critically important for
us to know just how difficult factoring is."	-I. Peterson

Anyone have any technical references to recent factoring algorithms?

Here are some technical references to recent primality testing algorithms:

R. Solovay and V. Strassen. A Fast Monte-Carlo Test for Primality.
	Siam Journal of Computing. 6(1977)84-85.

A.O.L. Atkin and R.G. Larson. On a Primality Test of Solovay and Strassen.
	Siam Journal of Computing. 11(1982)789-791.

Also, does anyone actually have some code that implements the Solovay and
Strassen test?

Here are some more references:

H. Cohen and H. W. Lenstra, Jr. Primality Testing and Jacobi Sums.
	Mathematics of Computation 42(1984)297-330.

L. M. Adelman, C. Pomerance, and R. S. Rumely, On distinguishing prime
	numbers from composite numbers. Annals of Math. 117(1983)173-206.

Thorkil Naur, New Integer Factorizations. Mathematics of Computation
	41(1983)687-695.

H. C. Williams, A p+1 Method of Factoring. Mathematics of Computation
	39(1982)225-234.

R. P. Brent, An improved Monte Carlo factorization algorithm.
	BIT 20(1980)176-184.

Richard K. Guy, How to factor a number. Congressus Numerantium XVI,
	Proc. Fifth Manitoba Conf on Numerical Math. Winnipeg. 1976 pp. 49-89.

H. C. Williams and J. S. Judd, Some Algorithms for prime testing using
	generalized Lehmer functions. Mathematics of Computation
	30(1976)867-886.

J. Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria
	and factorizations of 2^m+-1. Mathematics of Computation
	29(1975)620-647.

J. M. Pollard, Theorems on factorizations and primality testing,
	Proc. Cambridge Philos. Soc. 76(1974)521-528.

The MAA has a new book out that might be of interest:

Carl Pomerance, Lecture Notes on Primality Testing and Factoring,
	MAA Notes #4. 34 pp. Paperbound. List: $3.50.

A nice elementary survey of factoring techniques can be found in

H. C. Williams, Factoring on a Computer. The Mathematical Intelligencer.
	vol. 6 issue 3 (1984)29-36.

There is also a good bibliography.

Here are some more articles on factoring algorithms:

R. P. Brent and J. M. Pollard, Factorization of the eighth Fermat number,
	Math. Comp. 36(1981)627-630.

J. D. Dixon, Asymptotically fast factorization of integers, Math. Comp.
	36(1981)255-260.

J. L. Gerver, Factoring large numbers with a quadratic sieve, Math. Comp.
	41(1983)287-294.

M. A. Morrison and J. Brillhart, A method of factoring and the factorization
	of F7, Math. Comp. 29(1975)183-205.

J. M. Pollard, A Monte-Carlo method for factorizations, BIT 15(1975)331-334.

C. Pomerance and S. S. Wagstaff, Jr., Implementation of the continued fraction
	integer factoring algorithm, Proc. 12th Winnipeg Conf. on Numerical
	Methods and Computing(1982), Cong. Num. 37(1983)99-118.

C. P. Schorr, Refined analysis and improvements on some factoring algorithms,
	J. Algorithms 3(1982)101-127.