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.
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.