ni...@lysator.liu.se (Niels Möller) writes: I'm really not that familiar with state of the art factoring, but I'd guess pollard rho is a bad algorithm choice for that range, and one ought to use, e.g., some variant of the quadratic sieve.
Let me modify that statement somewhat. Pollars rho is suitable for finding small factors of any size composites. Small here might mean about < 2^64. Any factoring effort should start with trial division, then some rounds of Pollard rho, then perhaps some EC rounds. Only after that and when a remaining cofactor is non-prime, QS is to be rolled out. That could sound like the GMP code of coreutils factor is great for factoring really large numbers. It is, but only for smooth huge numbers. If we ever get crazy enough to consider QS for coreutils factor, its current GMP Pollard rho code would become part of a general factoring engine for numbers > 2^127. -- Torbjörn Please encrypt, key id 0xC8601622