Analysis of Average Running Times and Complexity in Root-Finding Algorithms for Polynomial Factorization

Abstract

This paper investigates the average running times and complexities of various root-finding algorithms, including the Affine Method (ARM), Sparse Root Algorithm (SRA), and Branching Tree Algorithm (BTA), in the context of polynomial factorization over finite fields. The algorithms are analyzed based on their ability to separate the roots of a polynomial into affine spaces of diminishing dimensions. We establish connections to the statistical properties of digital tries, allowing for an estimation of the expected height of the tree structures generated by these algorithms. Our findings reveal that ARM and BTA typically halt at a height related to the logarithm of the number of distinct roots, while SRA operates based on the degree of the polynomial. Additionally, we explore the implications of worst-case scenarios for ARM and propose improvements to its efficiency through partial precomputation techniques. The paper concludes by addressing the computational challenges associated with polynomial factorization, especially in cases where the degree is highly composite, and offers insights into potential optimizations for practical implementations of these algorithms.