Re: ellap: errors "impossible assignment I-->S" "not enough memory" "precision loss in truncation" "sorry, apell for p>10^25 is not yet implemented"

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

* Gaetan Bisson [2007-08-28 20:47]:
> I am encountering errors when trying to execute the following code.
> 
>   mc=ellinit([0,0,0,935824186433623028047894899424144532036848777,\
> 		   8985839528233295688881465643014243982999429660]);
>   ellap(mc,12542935105916320505274303565097221442462295713)
> 
> 
> Errors encountered depend on the architecture/version of PARI/GP:
> 
> Version 2.3.1 on i486 running linux (ix86/GMP-4.2.1 kernel) 32-bit.
>   *** ellap: impossible assignment I-->S
> 
> Version 2.3.0 on amd64 running linux (x86-64/GMP-4.1.4 kernel) 64-bit.
>   *** ellap: not enough memory
> 
> Version 2.1.1 on UltraSparc (MicroSparc kernel) 32-bit.
>   ***   precision loss in truncation
> 
> Version 2.0.15 on SuperSparc 32-bit.
>   ***   sorry, apell for p>10^25 is not yet implemented.
> 
> 
> If this helps, I actually know that this elliptic curve
> has trace 138 and discriminant -2312.

This still fails in the bleeding edge development version [Version 2.4.2
(development CHANGES-1.1861)]

(21:58) gp > e = ellinit([0,0,0,935824186433623028047894899424144532036848777,\
                          8985839528233295688881465643014243982999429660]);
(21:58) gp > p = 12542935105916320505274303565097221442462295713);
(21:58) gp > ellap(e,p)
  *** ellap: impossible assignment I-->S

It is expected, though:

(21:58) gp > ??ellap
ellap(E,p): [...]. If E/F_p  has  CM  by  a  principal  imaginary  quadratic
order we use an explicit formula   (involving  essentially Kronecker symbols
and Cornacchia's algorithm, hence very fast: O(log p)^2). Otherwise, we use
Shanks-Mestre's baby-step/giant-step  method,   which  runs in time O(p^{1/4})
using O(p^{1/4}) storage, hence becomes unreasonable when p has about 30
digits.
(21:58) gp > #Str(p)
%3 = 47

We are not in the CM case and p has 47 decimal digits, so we are "beyond
unreasonable" inputs for the naive algorithm.

The computation is still doable within PARI (in fact, easy) using the
external SEA package (1.5MB, GPL), which you can download from

  http://www.math.u-bordeaux.fr/~belabas/pari/scripts/ellsea.tar.gz

(21:58) gp > \r sea    \\ load the package. Actually done from my .gprc.
(21:58) gp > ? ellsea
ellsea(E,p,{flag1=0},{flag2=0}): returns the cardinality of the group of
rational points E(Fp) where E is an elliptic curve in ellinit format defined
over Z or Fp by the equation E: y^2 + a1*x*y + a3*y = x^3 + a2*x^2 + a4*x +
a6. If flag1 is equal to 1 the program displays information about the
computation process. [...]

(21:59) gp > ellsea(e, p, 1)
Computing the order of the elliptic curve
E:  y^2 = x^3 + 935824186433623028047894899424144532036848777*x + 8985839528233295688881465643014243982999429660
defined over the prime field of order 12542935105916320505274303565097221442462295713 (154bits)

Process prime 3.        Type: Elkies.    Compute trace mod 3, 9, 27
Process prime 5.        Type: Atkin.     Compute possible values for the trace
Process prime 7.        Type: Atkin.     Compute possible values for the trace
Process prime 11.       Type: Elkies.    Compute trace mod 11
Process prime 13.       Type: Atkin.     Compute possible values for the trace
Process prime 17.       Type: One root.  Compute trace mod 17
Process prime 19.       Type: Elkies.    Compute trace mod 19
Process prime 23.       Type: Atkin.     Compute possible values for the trace
Process prime 29.       Type: Atkin.     Compute possible values for the trace
Process prime 31.       Type: Atkin.     Compute possible values for the trace
Process prime 37.       Type: Atkin.     Compute possible values for the trace
Process prime 41.       Type: Elkies.    Compute trace mod 41
Process prime 43.       Type: Elkies.    Compute trace mod 43
Process prime 47.       Type: Atkin.     Compute possible values for the trace
Process prime 53.       Type: Atkin.     Compute possible values for the trace
Process prime 59.       Type: Elkies.    Compute trace mod 59
Process prime 61.       Type: Atkin.     Compute possible values for the trace

Computation of traces done. Entering match and sort algorithm.
time = 3,200 ms.
%5 = 12542935105916320505274303565097221442462295576
(21:59) gp > p + 1 - %
%6 = 138

Someday, this 'SEA' script shall become a true package like galdata
(Galois group computations) and elldata (Cremona's database).

Cheers,

    K.B.
--
Karim Belabas                  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`