Re: isprime(,2) (again, it seems)

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

On Thu, 3 Jul 2003, Phil Carmody wrote:
> Looking back through the dev archives (to Jan this year, but not further
> back, apologies if this has been mentioned before then)

It has not.

> it appears that the APRCL in 2.2.5 has a few problems when trying to prove
> some numbers of the form Phi(a,b).
>
> In particular there are two different failure modes.
>
> 1) ***   non invertible matrix in gauss,
>    e.g. gp > isprime(subst(polcyclo(16),x,16),2)
>
> 2) Digagreement with isprime(,1)
[...]
> (18:33) gp > isprime(subst(polcyclo(36),x,125),2)
> %7 = 0

Both of them were due to an integer overflow. They should be fixed in
the CVS version.

The APRCL code is currently in a sorry state: I spent a few days about one
year ago cleaning up the original (messy) code; then I received from the
original author further patches corresponding to mathematical improvements,
but which reintroduced many of the things I had painfully removed [ global
variables, various inefficiencies handling t_INTMODs and further unreadable /
undocumented hacks ].

The code was still preliminary [ did not contain the Bosma-van der
Hulst improvements, didn't use at all partial factorizations of p - 1, p + 1,
etc., used a very naïve way of tabulating discrete logs so that it is
completely unable to handle numbers around 2000 digits because of memory
overflow ]. I let it in as is, waiting for further patches.

Unfortunately the latter never came and the code is more or less orphaned at
this point. Ugrading it to a decent state would probably require at least one
week of my time (full time). I don't think I'll be able to muster that much
free time in the near future.

Anybody interested in cleaning up / improving that code ?

Cheers, and thanks for bringing this up,

    Karim.
-- 
Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dép. de Mathématiques, Bât. 425   Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud              http://www.math.u-psud.fr/~belabas/
F-91405 Orsay (France)            http://www.parigp-home.de/  [PARI/GP]