A p-adic algorithm to compute the Hilbert class polynomial

Опубликовано 7 сентября 2016, 16:49

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.