Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Univariate polynomial factorization over large finite fields

Abstract : 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.
Complete list of metadatas

https://hal.archives-ouvertes.fr/hal-03019847
Contributor : Joris van der Hoeven <>
Submitted on : Monday, November 23, 2020 - 3:38:52 PM
Last modification on : Wednesday, November 25, 2020 - 3:35:36 AM

File

fffact.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03019847, version 1

Collections

Citation

Joris van der Hoeven, Grégoire Lecerf. Univariate polynomial factorization over large finite fields. 2020. ⟨hal-03019847⟩

Share

Metrics

Record views

39

Files downloads

42