Re: Bug in apell?

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

On Wed, 8 Aug 2001, John Cremona wrote:
> The code
>
> e=ellinit([0, 460397952, 0, 275613539, 0],1)
> q=1185848623
> ellap(e,q)
>
> does not return a value after a long time (on either a 32 or a 64 bit
> machine).  The next prime q=1185848627 returns a value (67460)
> instantly.
>
> This came up in the middle of a big run where millions of curves had
> their points counted (literally), and this is the only example which
> caused a problem.
>
> Any ideas where the problem lies?  According to magma the correct answer
> (for the problem prime 1185848623) is -36184, and the group order is
> 1185884808 = (2^3)*(3)*(49411867).

There was a bug in the sorting phase of BS/GS (routine apell1()), due to an array
length being incorrectly updated.

[analysis and fix provided by Mark Dickinson; patch applies to versions 2.1 or
more recent]

Cheers,

    Karim.

diff -c -r1.23 -r1.24
*** src/modules/elliptic.c      2001/07/07 11:11:57     1.23
--- src/modules/elliptic.c      2001/08/26 07:21:25     1.24
***************
*** 1464,1474 ****
      /* look for h s.t f^h = 0 */
      if (bcon == gun)
      { /* first time: initialize */
!       tx = newbloc(s+1); *tx = evaltyp(t_VECSMALL) | evallg(s+1);
        ty = newbloc(s+1);
        ti = newbloc(s+1);
      }
      else f = powsell(cp4,f,bcon,p); /* F */
      if (!fh) goto FOUND;

      p1 = gcopy(fh);
--- 1464,1475 ----
      /* look for h s.t f^h = 0 */
      if (bcon == gun)
      { /* first time: initialize */
!       tx = newbloc(s+1);
        ty = newbloc(s+1);
        ti = newbloc(s+1);
      }
      else f = powsell(cp4,f,bcon,p); /* F */
+     *tx = evaltyp(t_VECSMALL) | evallg(s+1);
      if (!fh) goto FOUND;

      p1 = gcopy(fh);

-- 
Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
--
PARI/GP Home Page: http://www.parigp-home.de/