Interval Partitions and Polynomial Factorization

• Published in: Algorithmica 2012-06, Vol.63 (1-2), p.363-397
• Main Authors: von zur Gathen, Joachim, Panario, Daniel, Richmond, Bruce
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Exact sciences and technology; Mathematics; Mathematics of Computing; Numerical analysis; Numerical analysis. Scientific computation; Numerical approximation; Sciences and techniques of general use; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-011-9537-y

The fastest algorithms for factoring a univariate polynomial f of degree n over a finite field use a baby-step/giant-step approach. The set {1,…, n } of potential factor degrees is partitioned into intervals. In a first stage, for each interval the product of all irreducible factors with degree in the interval is determined, generalizing the method of Cantor & Zassenhaus. In a second stage, each polynomial corresponding to a multi-factor interval —containing two or more irreducible factors—is completely factored. The goal in this work is to analyze the behavior of this algorithm on uniformly random squarefree input polynomials, for various partitions. To this end, we study several parameters such as the expected number of multi-factor intervals, the expected number of irreducible factors with degrees lying in multi-factor intervals, the number of gcds executed in the factoring process, the expected total degree among the irreducible factors with degrees in multi-factor intervals, and the probability of a polynomial to have no multi-factor interval. We concentrate on partitions with polynomially growing interval sizes, and determine the partition that minimizes the expected number of gcds.