View Single Post
Old 2005-12-05, 21:23   #3
xilman's Avatar
May 2003
Down not across

3×3,529 Posts

Originally Posted by R.D. Silverman
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.
Good advice.

Arjen Lenstra implemented and I evaluated the use of ECM to split large cofactors. It was better than SQUFOF. We never tried mini-QS.

I even tried using Fermat to split the bicomposites, just for the fun of it. Somewhat to my surprise, it worked remarkably well. It uses such fast primitives that on numbers known to have two factors of similar magnitude it's almost competitive with SQUFOF. I did, of course, employ an early-abort strategy to avoid wasting too much time on any particular cofactor.

xilman is offline   Reply With Quote