Number Theoretic Algorithms For Elliptic Curves

Abstract

We present new algorithms related to both theoretical and practical questions in the area of elliptic curves and class field theory. The dissertation has two main parts, as described below. Let O be an imaginary quadratic order of discriminant D< 0, and let K be the associated quadratic imaginary field. The class polynomial H_D of O is the polynomial whose roots are precisely the j-invariants of elliptic curves with complex multiplication by O. Computing this polynomial is useful in constructing elliptic curves suitable for cryptography, as well as in the context of explicit class field theory. In the first part of the dissertation, we present an algorithm to compute H_D p-adically where p is a prime inert in K and not dividing D. This involves computing the canonical lift of a pair (E,f) where E is a supersingular elliptic curve and f is an embedding of O into the endomorphism ring of E. We also present an algorithm to compute H_D modulo p for p inert which is used in the Chinese remainder theorem algorithm to compute H_D. For an elliptic curve E over any field K, the Weil pairing is a bilinear map on the points of order n of E. The Weil pairing is a useful tool in both the theory of elliptic curves and the application of elliptic curves to cryptography. However, for K of characteristic p, the classical Weil pairing on the points of order p is trivial. In the second part of the dissertation, we consider E over the dual numbers of K and define a non-degenerate ``Weil pairing on p-torsion." We show that this pairing satisfies many of the same properties of the classical pairing. Moreover, we show that it directly relates to recent attacks on the discrete logarithm problem on the p-torsion subgroup of an elliptic curve over a finite field of characteristic p. We also present a new attack on the discrete logarithm problem on anomalous curves using a lift of E over the dual numbers of the finite field of p elements.