Johan Brinch on Tue, 02 Feb 2010 11:56:00 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: ellap hangs on a large-ish prime


On Tue, Feb 2, 2010 at 02:50, Jeremy Porter <porter.jeremy@gmail.com> wrote:
> In iteratively computing values of ellap(E,P) for the curve E =
> ellinit([0,0,1,-1,0]) for primes P of increasing size, I noticed that when P
> = 2486152157 my iteration would hang. Primes in a similar range (i.e.,
> nextprime(P+1) = 2486152159) are computed in well under a second, however I
> left this value of P to compute overnight without result.
>
> I initially noticed this when using libpari in a C program, then confirmed
> it with the GP calculator. An example follows:
>
> E = ellinit([0,0,1,-1,0]);
> P = 2486152157;
> isprime(P)
> ellap(E, nextprime(P+1))
> ellap(E, P)
>
>
> The first ellap() call gives me -25014 in 4ms. The second call does not
> return, and gives no error. The GP calculator was installed on an Ubuntu
> 9.10 system through the usual aptitude repositories, with the following
> header information:
>
> GP/PARI CALCULATOR Version 2.3.4 (released)
> i486 running linux (ix86/GMP-4.2.2 kernel) 32-bit version
> compiled: Nov  6 2008, gcc-4.3.3 20081030 (prerelease) (Ubuntu
> 4.3.2-2ubuntu1)
> (readline v5.2 enabled, extended help available)

Take a look at:
http://www.math.u-bordeaux1.fr/~belabas/pari/doc/faq.html#ellSEA

It states that versions prior to 2.4.3 uses an algorithm that can use
exponential running time on some primes.

-- 
Johan Brinch