A p-adic algorithm to compute the Hilbert class polynomial

January 29, 2007
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 P_D for a suitable discriminant D. The polynomial P_D has integer coefficients, and is the minimal polynomial of the modular j-value j(O_D) for the imaginary quadratic order O_D of discriminant D.

The polynomial P_D can be computed using complex analytic techniques. In this talk we present a new p-adic algorithm to compute P_D. 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.