View Single Post
Old 2009-03-18, 03:14   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

37×89 Posts
Default

Quote:
Originally Posted by mklasson View Post
Aliqueit could probably gain a good bit of overall speed from better ecm limits for all sizes of inputs. The current limits are basically a few half-decent guesses extrapolated to increasingly worse guesses. I don't know how optimal msieve's choices are. Maybe approximating that behaviour is a better start. Anyone with more knowledge of the matter care to chime in?
For smaller inputs, say less than 50 or 60 digits you could try just using msieve/yafu more. Msieve has good ecm choices for getting rid of small factors as does yafu, and the QS routines will quickly take care of the rest. For anything less than 60 digits you shouldn't be doing much ecm at all, IMO, assuming you first do trial division and pollard rho for a few hundred milliseconds. In yafu use the 'factor' function to automatically do this or something more customizable like siqs(rho(trial(N))).

For larger inputs say > 85 digits I'd start with the table in the GMP-ECM readme file and target doing ECM to, say, the 2/9*N digit level if the input is QSable or 1/3*N digit level if the input would otherwise need NFS.

In between 60 and 85 some ecm would be good to do. You may be able to get away with just calling msieve and letting it deal with the ecm'ing, but that assumes the user's msieve has that capability which it may not if home-built. Yafu's ecm is probably sufficiently slower at this point that gmp-ecm would be a good idea before QS.

Anyway, my $0.02.

- ben.

Last fiddled with by bsquared on 2009-03-18 at 03:16
bsquared is offline   Reply With Quote