Computing Hilbert Class Polynomials
We present and analyze two algorithms for computing the Hilbert class polynomial H_D(X). The first is a p-adic lifting algorithm for inert primes p in the order of discriminant D < 0. The second is an improved Chinese remainder algorithm which uses the class group action on CM-curves over finite fields. Our run time analysis gives tighter bounds for the complexity of all known algorithms for computing H_D(X), and we show that all methods have comparable run times.
Modular polynomials for genus 2
Modular polynomials are an important tool in many algorithms involving elliptic curves. In this article we generalize this concept to the genus 2 case. We give the theoretical framework describing the genus 2 modular polynomials and discuss how to explicitly compute them.