This chapter describes the specialised facilities for elliptic curves defined over finite fields. Details concerning their construction, arithmetic, and basic properties may be found in Chapter ELLIPTIC CURVES. Most of the machinery has been constructed with Elliptic Curve Cryptography in mind.
The first major group of intrinsics relate to the determination of the order of the group of rational points of an elliptic curve over a large finite field. A variety of canonical lift algorithms are provided for characteristic 2 fields while the SEA algorithm is used for fields having characteristic greater than 2. These tools are used as the basis for functions that search for curves suitable for cryptographic applications.
A function for computing the Weil pairing forms the basis of the MOV reduction of the discrete logarithm problem (DLP) for a supersingular elliptic curve to a DLP in a finite field. A second type of attack on the DLP is based on the use of Weil descent. Tools implementing a generalisation of the GHS attack for ordinary curves in characteristic 2 are provided.
Finally, for a direct attack on the DLP for elliptic curves, a parallel collision search version of the Pollard rho algorithm is available.