Jacobian varieties of hyperelliptic curves are a generalization of elliptic curves that are just as suitable for efficient computations and cryptographic applications. Their endomorphism ring plays a central role in applications such as constructing varieties with a prescribed cardinality over a prescribed finite field.

We will present the first subexponential-time algorithm for computing the endomorphism ring structure of ordinary varieties of dimension one and two over finite fields. It exploits the relationship between subgroups of a variety and the ideal class group of its endomorphism ring, which is known as complex multiplication theory.

For one-dimensional varieties, that is, elliptic curves, this algorithm is very efficient and its complexity can be rigorously proven under just the generalized Riemann hypothesis. In higher dimension, additional heuristics are required, but the algorithm is nevertheless able to perform record endomorphism ring computations.