View Single Post
Old 2005-12-05, 19:30   #2
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

22×5×373 Posts

Originally Posted by ThiloHarich
I have Implemented the MPQS.
After sieving you have to decomposit the generated values into the primes.
By most algorithms (i read) this is done by trial division (so do I).
This stage uses the same time as the sieving step (i have tested this only on small inputs around 40 Digits).

Which of the known factoring algorithms is recommended for this step?
Do the factoring by resieving.

Save the locations you believe are smooth.
Resieve. Whenever you hit a location that you think is smooth,
instead of accumulating a scaled logarithm of the prime, save the prime itself.

Split the large cofactors by a 'tiny' QS that does not use the large
prime variation. Although for composites of (say) less than 60 digits,
SQUFOF will be almost as fast.
R.D. Silverman is offline   Reply With Quote