Preprints

1. Algorithms for computing norms and characteristic polynomials on general Drinfeld modules

   With Xavier Caruso · July 2023 · arXiv HAL

   Abstract

   We provide two families of algorithms to compute characteristic polynomials of endomorphisms and norms of isogenies of Drinfeld modules. Our algorithms work for Drinfeld modules of any rank, defined over any base curve. When the base curve is ℙ1𝔽q, we do a thorough study of the complexity, demonstrating that our algorithms are, in many cases, the most asymptotically performant. The first family of algorithms relies on the correspondence between Drinfeld modules and Anderson motives, reducing the computation to linear algebra over a polynomial ring. The second family, available only for the Frobenius endomorphism, is based on a new formula expressing the characteristic polynomial of the Frobenius as a reduced norm in a central simple algebra.

   

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

   With Pierre-Jean Spaenlehauer · July 2022 · arXiv HAL IACR

   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 Fq 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 Fq[X]-modules, which is solvable in polynomial time thanks to an algorithm by Wesolowski.

   Comments

   This paper is a rewrite of arXiv:2203.06970v2. It takes into account the recent attack of Wesolowski on the cryptographic applications we proposed in the original preprint. All mathematical and algorithmic statements are the same as in the original preprint; we removed cryptographic applications, and the introduction and experimental results have been widely rewritten. The arXiv and Hal submissions are updated; the IACR eprint submission will remain unchanged.

   

Publications

1. Drinfeld modules in SageMath

   With David Ayotte, Xavier Caruso, Joseph Musleh · ACM Communications in Computer Algebra, Vol. 57, No. 2 (ISSAC'23 Software presentation) · April 2023 · ACM arXiv HAL

   Abstract

   We present the first implementation of Drinfeld modules fully integrated in the SageMath ecosystem. First features will be released with SageMath 10.0.