Fix an ordinary abelian variety defined over a finite field. The ideal classgroup of its endomorphism ring acts freely on the set of isogenous varietieswith same endomorphism ring, by complex multiplication. Any subgroup of theclass group, and generating set thereof, induces an isogeny graph on the orbitof the variety for this subgroup. We compute (under the Generalized RiemannHypothesis) some bounds on the norms of prime ideals generating it, such thatthe associated graph has good expansion properties. We use these graphs, together with a recent algorithm of Dudeanu, Jetchev andRobert for computing explicit isogenies in genus 2, to prove randomself-reducibility of the discrete logarithm problem within the subclasses ofprincipally polarizable ordinary abelian surfaces with fixed endomorphism ring.In addition, we remove the heuristics in the complexity analysis of analgorithm of Galbraith for explicitly computing isogenies between two ellipticcurves in the same isogeny class, and extend it to a more general settingincluding genus 2.
展开▼
