Computing a Group Action from the Class Field Theory of Imaginary Hyperelliptic Function Fields

2022/03/14 by Leudière, Antoine, Spaenlehauer, Pierre-Jean
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Symbolic Computation (cs.SC)

paper · doi:10.48550/arxiv.2203.06970

Abstract

We explore algorithmic aspects of a simply transitive commutative group action coming from the class field theory of imaginary hyperelliptic function fields. Namely, the Jacobian of an imaginary hyperelliptic curve defined over \mathbb F_q acts on a subset of isomorphism classes of Drinfeld modules. We describe an algorithm to compute the group action efficiently. This is a function field analog of the Couveignes-Rostovtsev-Stolbunov group action. We report on an explicit computation done with our proof-of-concept C++/NTL implementation; it took a fraction of a second on a standard computer. We prove that the problem of inverting the group action reduces to the problem of finding isogenies of fixed τ-degree between Drinfeld \mathbb F_q[X]-modules, which is solvable in polynomial time thanks to an algorithm by Wesolowski. We give asymptotic complexity bounds for all algorithms presented in this paper.

Related

• Computing the Automorphism Groups of Hyperelliptic Function Fields
• Governing fields for hyperelliptic function fields
• Drinfeld modules as noncommutative tori
• Explicit Class Field Theory for global function fields
• Class groups of imaginary biquadratic fields