A p-adic algorithm to compute the Hilbert class polynomial

  • Reinier Broker | University of Calgary

A classical approach of constructing elliptic curves that can be used for cryptographic purposes relies on the theory of complex multiplication. A key ingredient in the algorithm is to compute the Hilbert class polynomial PD for a suitable discriminant D. The polynomial PD has integer coefficients, and is the minimal polynomial of the modular j-value j(OD) for the imaginary quadratic order OD of discriminant D.

The polynomial PD can be computed using complex analytic techniques. In this talk we present a new p-adic algorithm to compute PD. One of the advantages of working over a p-adic field is that we do not have to worry about rounding errors, and the p-adic algorithm is the first algorithm with a rigorous run time analysis. When implemented carefully, the p-adic algorithm is very fast in practice and easily competes with the complex analytic approach. Many examples will be given.

Speaker Details

I studied mathematics in Amsterdam and did my PhD in Leiden, The Netherlands. The topic of my PhD-research is algorithmic questions in number theory and arithmetic geometry. After finishing my thesis in the spring in 2006, I was a visiting member of the Fields Institute in Toronto. Since January 2007, I am working at the University of Calgary.

    • Portrait of Jeff Running

      Jeff Running

    • Portrait of Reinier Broker

      Reinier Broker

Watch Next