Overview of Factoring Algorithms

[ThiloHarich]

Is there a List of Factoring Algorithms and running timings, which answers the Question in which case should we use which Algorithm?

Interesting parameter of the Algorithms might be:
- Memory used
- Length of the numbers occurring while calculation the Factorization
- it is the fastest Algorithm under the following conditions

I start a short List here

let p be the biggest prime of a factorization.

Trial Division
time: L_n(1,1/2), p
memory: O (ln(n))
bits:ln (n)
very small n or p very small (how small?)

Fermat
time: L_n(1,1/2), (sqrt (n)-p)^2/sqrt(n)
memory: O (ln(n))
bits: ln (n)
p near sqrt(n)

Pollard Rho
time:L_n(1,1/4), sqrt (p)
memory: O (ln(n))
bits: ln (n)
small n, small p

SQUFOF
time:L_n(1,1/4), sqrt (p)
memory: O (ln(n))
bits: 1/2 ln (n) ?

SIQS
time:L_n(1/2,1)
memory: L_n(1/2,1)
bits: log (n) (only for sieving)
for general number up to 110 digits.

gcd
time: L_n(1,1/2), p*ln (p)^2, amortized ln (p)^2
memory: p
bits: p
if the sum of lengths of the numbers we want to factorize is longer then the length of the product of possible factors.

The gcd method is the method described by bernstein in http://cr.yp.to.mirror.dogmap.org/fa...s-20040510.pdf
with amortized I denote the time needed for each bit of an set of integers (which has more then p bits).

A special question is which is the best method for factorizing Integers that remain after a sieving phase?
If we have p Integers with less then ln (n) bits which have passed the sieving phase, we have the following theoretical timings:

Trial Division and Resieving: p^2,
Pollard Rho and SQUFOF: p^1.5
gcd: p * ln (p)^2

In practice Resieving is fast, since we have rather simple Operations.
The gcd method is slower then Pollard Rho for p < 30,000. Since FFT beats Karatsuba (running time p^1.585) for inputs greater then 30,000 digits. So the gdc method should be faster then PollarRho for n around 10^40.
I read that SQUFOF is faster then Pollard Rho. How much?