𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Deterministic Complexity of Factoring Polynomials

✍ Scribed by Shuhong Gao

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
345 KB
Volume
31
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

✦ Synopsis

The paper focuses on the deterministic complexity of factoring polynomials over finite fields assuming the extended Riemann hypothesis (ERH). By the works of and , the general problem reduces deterministically in polynomial time to finding a proper factor of any squarefree and completely splitting polynomial over a prime field Fp. Algorithms are designed to split such polynomials. It is proved that a proper factor of a polynomial can be found deterministically in polynomial time, under ERH, if its roots do not satisfy some stringent condition, called super square balanced. It is conjectured that super square balanced polynomials do not exist.

πŸ“œ SIMILAR VOLUMES

Factorization of the Cover Polynomial
Factorization of the Cover Polynomial
✍ Morris Dworkin πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 496 KB

Chung and Graham's cover polynomial is a generalization of the factorial rook polynomial in which the second variable keeps track of cycles. We factor the cover polynomial completely for Ferrers boards with either increasing or decreasing column heights. For column-permuted Ferrers boards, we find a

Complex Zolotarev Polynomials on the Rea
Complex Zolotarev Polynomials on the Real Interval [βˆ’1, 1]
✍ C. Detaille; J.P. Thiran πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 321 KB

We consider complex Zolotarev polynomials of degree \(n\) on \([-1,1]\), i.e., monic polynomials of degree \(n\) with the second coefficient assigned to a given complex number \(\rho\), that have minimum Chebyshev norm on \([-1,1]\). They can be characterized either by \(n\) or by \(n+1\) extremal p

On Valuations, the Characteristic Polyno
On Valuations, the Characteristic Polynomial, and Complex Subspace Arrangements
✍ Richard Ehrenborg; Margaret A. Readdy πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 203 KB

We present a new combinatorial method to determine the characteristic polynomial of any subspace arrangement that is defined over an infinite field, generalizing the work of Blass and Sagan. Our methods stem from the theory of valuations and Groemer's integral theorem. As a corollary of our main the