Re: A bug with factorint?

[Gerhard Niklasch <nikl@mathematik.tu-muenchen.de>]

In response to:
> Date: Tue, 29 Jan 2002 03:10:56 +0100
> Subject: A bug with factorint?
> From: "Juan Luis Varona Malumbres" <jvarona@dmc.unirioja.es>
> Message-Id: <6E414881-145D-11D6-AC0B-003065EB0050@dmc.unirioja.es>

...
> I get the following problem (I abbreviate 
> with ..............................):
...
> ECM: dsn = 72,	B1 = 1073500,	B2 = 118085000,	gss = 1024*420
> ECM: time = 23306030 ms, B1 phase done, p = 1073507, setting up for B2
> ECM: time =   1020 ms, entering B2 phase, p = 1073717
> ECM: time = 22841090 ms
> ECM: dsn = 72,	B1 = 1073500,	B2 = 118085000,	gss = 1024*420
> ECM: time = 23374350 ms, B1 phase done, p = 1073507, setting up for B2
> ECM: time =    960 ms, entering B2 phase, p = 1073717
> .......
> and it continues in the same way.
> 
> That is: the eliptic curve method with dsn = 72 appears again and again.

This is sort of intentional.  dsn=72 points at the largest set of
parameters which the present ECM implementation knows about in its
tables  (this being due in part to memory consumption and in part
to the need for the auxiliary primes to fit into one word),  so we
don't escalate beyond this point.  Moreover, due to number of curves
used vs. parameter growth, we still haven't exhausted the range of
potential factors visible to ECM at this parameter size, so we still
have a (small) chance of finding something despite the repeated para-
meter choices.

> We never reach MPQS method.

That is true only for large values of "never". :)  ECM in fact told
you in advance that it was going to try for 38 iterations.

You can suppress the ECM stage before MPQS through the flag argument
to factorint  (use 6),  but MPQS on a 95-bit number with the present
implementation will require on the order of many months  (sufficient
memory assumed, and a stable system and reliable power supply) - enough
to justify spending 3 weeks on ECM first, although this looks counter-
intuitive to us impatient human spectators.

Your best bet at present, if you want to do this with gp, is to
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