Igor Schein on Mon, 25 Mar 2002 19:19:59 -0500


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: A bug with factorint?


On Tue, Jan 29, 2002 at 09:41:57AM +0100, Gerhard Niklasch wrote:
[snip]
> Your best bet at present, if you want to do this with gp, is to

Yes, the big *if*.  With all credits due to Gerhard for implementing
an excellent, robust and well-intergrated factorization mechanism in
pari/gp, it is not (unfortunately) the fastest available
implementation of either ECM or MPQS.  In particular, implementation
of ECM available from ECMNET has been greatly superior to our ECM in
my experience.  As far as MPQS, it's inferior, in particular, to
Parallel Prime MPQS algorithm, implemented by Satoshi Tomabechi.
Maybe one day Gerhard will be able allocate a time slot from his busy
schedule to implement PPMPQS in pari, but as of now one should be
aware of alternative venues.  And, returning back to ECM issue,
there's too much difference between the front ends of 2 implementations
to make a fair citrus-to-citrus comparison, but every time I run them
side by side on the same input, ECMNET implementation is always far
ahead.   

> attempt the factorization simultaneously on two machines with
> different flag settings, so that one will keep churning away
> with ECM while the other embarks on MPQS.  You'll find that this
> ECM stage will give up long before MPQS approaches the Gaussian
> elimination phase.  Of course, you can run software more specialized
> towards integer factorization simultaneously on a third machine...
> 
> Cheers, Gerhard

Igor

P.S.

Actually, there's one feature that I always wanted to see in gp -
optionally, automatically add factors found during factorization to
the prime table, given there's no more limitation of 100 entries in
addprimes().  1 problem I can see is what to do if ^C has been
pressed in the middle of factorization, but I guess it's a matter of
choice.