Number theoretic algorithms for elliptic curves

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 = QD . The class polynomial HD 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 HD p-adically where p is a prime inert in K and not dividing D. This involves computing the canonical lift E˜ 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 HD modulo p for p inert which is used in the Chinese remainder theorem algorithm to compute HD.;For an elliptic curve E over any field K, the Weil pairing en 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 K[epsilon] 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 the finite field Fq . We also present a new attack on the discrete logarithm problem on anomalous curves using a lift of E over Fp [epsilon].