Elliptic Curves: Operations over F_q

In the case of elliptic curves defined over a finite field, specialised functions are provided for the construction and analysis of maps. The major algorithm for such curves is the SEA algorithm for point counting.

• Characterization of ordinary and supersingular elliptic curves
• Representative supersingular curve
• Enumeration of all points (small fields), random point
• Quadratic twist, all quadratic twist, all twists
• Order of a point via baby-step giant-step
• Schoof-Elkies-Atkin (SEA) algorithm for finding the order of the group of rational points
• Schoof-Elkies-Atkin (SEA) algorithm with early abort facility for searching for cryptographically secure curves
• Lercier's extension of the SEA algorithm for finite fields of characteristic two
• Structure of the abelian group of rational points
• Zeta function of a curve
• Discrete logarithm (parallel collision search version of the Pollard rho algorithm)
• Weil pairing

For a random curve taken over a 168-bit prime field GF(p), Magma takes an average of 47 seconds to determine the order of the group. In the case of a random curve taken over a 400-bit prime field the average runtime is 2200 seconds.