✦ LIBER ✦

Improved Techniques for Factoring Univariate Polynomials

✍ Scribed by GEORGE E. COLLINS; MARK J. ENCARNACIÓN

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 563 KB
Volume: 21
Category: Article
ISSN: 0747-7171
DOI: 10.1006/jsco.1996.0014

No coin nor oath required. For personal study only.

✦ Synopsis

The paper describes improved techniques for factoring univariate polynomials over the integers. The authors modify the usual linear method for lifting modular polynomial factorizations so that efficient early factor detection can be performed. The new lifting method is universally faster than the classical quadratic method, and is faster than a linear method due to Wang, provided we lift sufficiently high. Early factor detection is made more effective by also testing combinations of modular factors, rather than just single modular factors. Various heuristics are presented that reduce the cost of the factor testing or that increase the chance of successful testing. Both theoretical and empirical computing times are presented.

📜 SIMILAR VOLUMES

Sparse shifts for univariate polynomials

✍ Y. N. Lakshman; B. David Saunders 📂 Article 📅 1996 🏛 Springer 🌐 English ⚖ 840 KB

Sparse Shifts for Univariate Polynomials

✍ Y. N. Lakshman; B. David Saunders 📂 Article 📅 1997 🏛 Springer 🌐 English ⚖ 90 KB

On Samelson's iteration for factoring po

On Samelson's iteration for factoring polynomials

✍ G. W. Stewart 📂 Article 📅 1970 🏛 Springer-Verlag 🌐 English ⚖ 397 KB

Univariate Polynomials: Nearly Optimal A

Univariate Polynomials: Nearly Optimal Algorithms for Numerical Factorization and Root-finding

✍ Victor Y. Pan 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 552 KB

To approximate all roots (zeros) of a univariate polynomial, we develop two effective algorithms and combine them in a single recursive process. One algorithm computes a basic well isolated zero-free annulus on the complex plane, whereas another algorithm numerically splits the input polynomial of t

A heuristic irreducibility test for univ

A heuristic irreducibility test for univariate polynomials

✍ Michael B. Monagan 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 610 KB

Efficient p-adic Cell Decompositions for

Efficient p-adic Cell Decompositions for Univariate Polynomials

✍ Michael Maller; Jennifer Whitehead 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 177 KB

Cell decompositions are constructed for polynomials f (x) # Z p [x] of degree n, such that n< p, using O(n 2 ) cells. When f is square-free this yields a polynomialtime algorithm for counting and approximating roots in Z p . These results extend to give a polynomial-time algorithm in the bit model f