International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Reinier Broker

Publications

Year
Venue
Title
2008
EPRINT
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.
2008
EPRINT
Modular polynomials for genus 2
Reinier Broker Kristin E. Lauter
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.