Modulo Errors

I’ve spent the last few weeks getting my head around the SEA algorithm- a series of techniques for computing cardinality of elliptic curves over finite fields. The basic Schoof algorithm (the S of SEA) is based on the Weil conjectures, from which to find the cardinality it suffices to determine the trace of Frobenius, t. This can be shown to fall within certain bounds and thus (by the chinese remainder theorem) the problem can be solved by establishing t modulo l for a series of smaller primes l. The contributions by Elkies and Atkin make these subcalculations feasible, but trade computational complexity for mathematical difficulty, and it’s these I’ve been grappling with recently- particularly the Elkies approach.

Fortunately there is an excellent book - Blake, Seroussi and Smart’s Elliptic Curves in Cryptography which covers this topic thoroughly. As usual, attempting to implement the procedures myself has uncovered (and repaired) many gaps in my comprehension of the algorithms involved. I’m finally getting correct answers, albeit for small examples, so I’ve written up some summary notes on the book and a worked example in Maple. It still requires a high degree of interaction to get to the final result; my understanding is that SAGE (on linux) implements the SEA algorithm, so it doesn’t seem worth trying to tie it all together into a standalone Maple procedure- this would be a programming challenge, but wouldn’t add anything to my mathematical understanding!

Notes: [SEA.dvi]
Appendix (Maple procedures): [SEA_tools.mpl]
Example (Maple worksheet): [SEA.mw]

This entry was posted on Wednesday, March 14th, 2007 at 12:32 pm and is filed under Algebraic Geometry, Algorithms, Maple, Number Theory, PhD.