Yes, you can use SEA with 100 digit prime field orders!

0 views
Skip to first unread message

Joanna

unread,
Dec 9, 2010, 12:29:14 AM12/9/10
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
Reply all
Reply to author
Forward
0 new messages