Univariate polynomial factorization over finite fields with large extension degree

The best known asymptotic bit complexity bound for factoring univariate polynomials over finite fields grows with d 1.5 + o ( 1 ) for input polynomials of degree d , and with the square of the bit size of the ground field. It relies on a variant of the Cantor–Zassenhaus algorithm which exploits fast...

Full description

Saved in:
Bibliographic Details
Published in:Applicable algebra in engineering, communication and computing communication and computing, 2024-03, Vol.35 (2), p.121-149
Main Authors: Hoeven, Joris van der, Lecerf, Grégoire
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Computer Hardware
Computer Science
Fields (mathematics)
Original Paper
Polynomials
Symbolic and Algebraic Manipulation
Theory of Computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The best known asymptotic bit complexity bound for factoring univariate polynomials over finite fields grows with d 1.5 + o ( 1 ) for input polynomials of degree d , and with the square of the bit size 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.
ISSN:0938-1279
1432-0622
DOI:10.1007/s00200-021-00536-1