Xref: utzoo sci.math:3485 sci.crypt:1038
Path: utzoo!mnetor!uunet!mcvax!walter
From: walter@cwi.nl (Walter M. Lioen)
Newsgroups: sci.math,sci.crypt
Subject: Re: New Factorization Records
Message-ID: <7537@boring.cwi.nl>
Date: 26 Apr 88 10:43:33 GMT
References: <7535@boring.cwi.nl> <2675@phoenix.Princeton.EDU>
Organization: CWI, Amsterdam
Lines: 33
Keywords: 4,6,8,9,10,12,14,15,16,18,...

In article <2675@phoenix.Princeton.EDU>
schoen@phoenix.Princeton.EDU (Randy Schoenberg) asks:

> Is it chance that your program factored in such a relatively short time?
> Or can you gurantee a solution after a certain (reasonable) amount of time.

See the explanation of "general purpose algorithm" below.

> Can you provide an average amount of time for factoring numbers of length n?

Adding 3 digits roughly doubles the run time for n near 90 decimal digits.
This factor of 2 drops (very!) slowly as n tends to infinity.

> I am asking because you say that you used general purpose algorithms and I'm
> not sure what you mean by general.

General purpose algorithms, run in deterministic time depending only on the
size of the number being factored and are guaranteed to succeed regardless
of the size of the factors.
The method we used is known as the "Multiple Polynomial Quadratic Sieve"
method (MPQS).

Special purpose algorithms depend on luck but, on the other hand, have
factored larger numbers. They also depend upon the number being factored
having small prime factors, and are generally useless if the number being
factored is the product of two, nearly equal, primes.
The well known "Elliptic Curve Method" (ECM) is an example of such a
probabilistic method.
-- 
Walter M. Lioen,
CWI, P.O. Box 4079, 1009 AB  Amsterdam, The Netherlands.
INTERNET:    walter@cwi.nl
BITNET/EARN: walter@mcvax