From: womack@ox.compsoc.org.uk (Tom Womack)
Newsgroups: sci.math
Subject: Re: continued fraction algorithm
Date: 16 May 1997 20:01:28 GMT

Harden (wharden@mail.mia.bellsouth.net) wrote:
: What is known about the average and worst-case running times of the 3 
: major integer factoring algorithms in use today( ECM,NFS,QS ) and how do 
: they compare to the continued fraction algorithm?

ECM and QS, CFRAC : O(exp(K*sqrt(log n * loglog n)))

K=1 for QS, I think; maybe K is slightly more for ECM. K=sqrt(2) comes to
mind for CFRAC.

NFS : O(exp(K*log(n)^1/3 * loglog(n)^2/3)); K is about 2.

The advantage of QS over CFRAC is that you can parallelise very easily;
there's only one continued fraction for a number, but there are myriads
of possible polynomials.

Tom