Re: Rho bug (was Re: [PARI] MPQS error message: complement)

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

In response to
> Message-ID:
> 	<Pine.LNX.3.95.980830222529.29091E-100000@pev.math.univ-montp2.fr>
> Date: Sun, 30 Aug 1998 22:43:00 +0200 (MET DST)
> From: Philippe Elbaz-Vincent <pev@pev.math.univ-montp2.fr>

> ? factorint(6812991403,1)
> IFAC: factorizer returned strange object to ifac_crack
> 00000007

This is known  (Henri Cohen found another number which triggered it)
and fixed for 2.0.12.  If you're interested in a sneak preview, you
may download
   ftp://hasse.mathematik.tu-muenchen.de/incoming/ifactor1.c.gz
make sure it is gunzip-ped either by your browser or manually,
and replace the existing src/basemath/ifactor1.c with it  (it should
work cleanly inside 2.0.11 surroundings).  Apart from fixing this
little problem, it also features an extensively modified and re-tuned
ECM factorizer, with many thanks to Paul Zimmermann for being per-
sistently dissatisfied with the previous algorithm and offering lots
of advice and references.

The correct diagnostic output for this number should look like this:
---8<---
Rho: searching small factor of 33-bit integer
Rho: using X^2-1 for up to 14 rounds of 32 iterations
Rho: time =     10 ms,   11 rounds,
        Pollard-Brent failed.
Rho: restarting for remaining rounds...
Rho: using X^2+3 for up to 3 rounds of 32 iterations
Rho: time =      0 ms,  Pollard-Brent giving up.
--->8---
(and, with the flag set to 1, it will proceed to split the number using
ECM in another 60msec or so).  The bug was in a few missing re-initiali-
zations when Rho had to restart because the first attempt had `found'
both factors at exactly the same iteration, failing to separate them.

By the way, factorint(6812991403,4)  (i.e. using MPQS and skipping the
Pollard Rho phase)  takes only about 10(+-10) msec on my P133;  this
increases to 40 or 60 msec when diagnostics are turned on.

Enjoy, Gerhard