International Association
for Cryptologic Research

We present a generalization to genus 2 of the probabilistic

algorithm in Sutherland~\\cite{Sutherland} for computing Hilbert class polynomial˻s. The improvement over the algorithm presented

in~\\cite{BGL} for the genus 2 case, is that we do not need to find a

curve in the isogeny class with endomorphism ring which is the maximal

order: rather we present a probabilistic algorithm for ``going up\'\' to a {\\it

maximal} curve (a curve with maximal endomorphism ring), once we find {\\it

any} curve in the right isogeny class. Then we use the structure of the

Shimura class group and the computation of $(\\ell,\\ell)$-isogenies to

compute all isogenous maximal curves from an initial one.