Joanna
unread,Dec 9, 2010, 12:29:14 AM12/9/10Sign in to reply to author
Sign in to forward
You do not have permission to delete messages in this group
Either email addresses are anonymous for this group or you need the view member email addresses permission to view the original message
to 581d-2010
To set the record straight, Schoof-Elkies-Atkin is reasonable to use
on 100 digit primes. (I got '23' from the first value of a loop that
just hanged (it should have given the timings for each #E/K
calculation as it did it, but didn't) -- sorry -- couldn't think!)
Anyhow, in Sage, E.cardinality_pari(), uses two other algorithms (an
"explicit" O((log p)^2) formula when E has CM by a principal
imaginary
quadratic order, BSGS for small primes), and SEA for larger
primes. They say primes up to about 200 should be feasible.
For rough times, they give:
E.cardinality_pari(): 80 digits: 7.7 s, 100: 22.5 s, 120: 76.3 s,
130: fail
E.cardinality_bsgs(): 20 digits: 7.21 s, 25: 57.1 s, 30: hang
-- Joanna