Univariate polynomial factorization over large finite fields

Joris van der Hoeven (1, 2) , Grégoire Lecerf (1, 2)

1 CNRS - Centre National de la Recherche Scientifique
2 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]

The best known asymptotic bit complexity bound for factoring univariate polynomials over finite fields grows with the input degree to a power close to 1.5, and with the square of the bitsize of the ground field. It relies on a variant of the Cantor-Zassenhaus algorithm which exploits fast modular composition. Using techniques by Kaltofen and Shoup, we prove a refinement of this bound when the finite field has a large extension degree over its prime field. We also present fast practical algorithms for the case when the extension degree is smooth.

Domaines: Complexité [cs.CC]; Calcul formel [cs.SC]; Logiciel mathématique [cs.MS]; Algèbre commutative [math.AC]; Arithmétique des ordinateurs

Joris van der Hoeven, Grégoire Lecerf. Univariate polynomial factorization over large finite fields. Applicable Algebra in Engineering, Communication and Computing, 2022, ⟨10.1007/s00200-021-00536-1⟩. ⟨hal-03019847⟩