Re: GP: ffinit() bug

[Bill Allombert <allomber@math.u-bordeaux.fr>]

On Mon, Apr 29, 2002 at 10:48:55PM -0400, Michael Somos wrote:
> Pari Developers,
>      Using the up-to-the-minute CVS I find :
> 
> ? \v
>                  GP/PARI CALCULATOR Version 2.2.3 (development)
>                  UltraSparc (MicroSparc kernel) 32-bit version
>               (readline v2.2 enabled, extended help not available)
> ? ffinit(4,2)
> ^C  ***   user interrupt after 23,010 ms.
> 
> which appears to be an infinite loop. Shalom, Michael

4 is not a prime number, so the behaviour of ffinit is undefined in this case.
Maybe the doc is misleading, it is written F_p, and F_4 make sense, but
it is universally agreed that p is a prime else we wrote F_q, I think.

Testing the primality of p is not a option, since the new ffinit
is much faster than ispseudoprime or even BSW_psp() for large p.

? p=2^521-1;
? install(BSW_psp,lG);
? BSW_psp(p);
%2 = 1
? ##
  ***   last result computed in 30 ms.
? ffinit(p,10);
? ##
  ***   last result computed in 0 ms.

Fixing the oo-loop is a little difficult.  The algorithm looks for a odd prime
number l so that 4 is not a square modulo l.  Of course it will never find it,
but that give no information on the fact that 4 is not a prime, unless we use
Lagarias-Odlyzko bound but this is not really practical.

Cheers,

Bill.

PS: there is a CVS branch for the stable version named 'release-2-1-patches'.
You can also check it out if you are interested.