Re: Re: APRCL e(t) table

[tom@womack.net]

On Feb 3, 2009, Bill.Allombert@math.u-bordeaux1.fr wrote: 
>On Mon, Feb 02, 2009 at 04:32:27PM +0000, tom@womack.net wrote:
>> I am very impressed with the speed of the pari APRCL implementation -
>> it beats by a long way the best public ECPP implementations, and looks

> Really ? I find that rather unexpected and vaguely alarming. 

I've tested against Morain's ecpp-6.4.5 and got other people to test against primo on Windows; I suspect part of the issue is that those implementations are distributed as 32-bit executables so don't get the benefit of 64-bit libgmp arithmetic.  There is no open-source ECPP implementation that I'm aware of, unless Franke's fastECPP happens to be open source and he didn't mention this in the paper.

On the same hardware, I find that ecpp for 10^500+961 takes 428.2 seconds and isprime(10^500+961,2) under pari takes 93.8.  For 10^800+1537 the timings are 1537 seconds for ECPP and 508.3 for pari.

>> I've computed e(t) (with my
>> own code checked against pari's results) for t<10^9 and am doing it
>> for t<10^11 with 5040|t; would you be interested in an improved e(t)
>> table capable of handling at least N<10^5512.7 and probably well
>> beyond ? I should have it ready by the end of the week.

> Well, it would certainly be interesting!

I notice that my computation of e(t) didn't throw away cases where there are divisors with d+1 prime and greater than five million, whilst pari's does.  Was this intended as a memory- and computation-saving measure, or is it required for the correctness of the algorithm?  It's really quite a serious restriction for t>10^9 or so.

I'll need to do a little more instrumentation, but it seems as if efficient cyclotomic-modulus code for 7,11,13,17 might make a difference.

Tom