๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Factoring Modular Polynomials

โœ Scribed by J. VON ZUR GATHEN; S. HARTLIEB

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
642 KB
Volume
26
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

โœฆ Synopsis

This paper gives an algorithm to factor a polynomial f (in one variable) over rings like Z /rZ for r โˆˆ Z or F q [y]/rF q [y] for r โˆˆ F q [y]. The Chinese Remainder Theorem reduces our problem to the case where r is a prime power. Then factorization is not unique, but if r does not divide the discriminant of f , our (probabilistic) algorithm produces a description of all (possibly exponentially many) factorizations into irreducible factors in polynomial time. If r divides the discriminant, we only know how to factor by exhaustive search, in exponential time.

๐Ÿ“œ SIMILAR VOLUMES

Factoring distance matrix polynomials
Factoring distance matrix polynomials
โœ Karen L. Collins ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 584 KB
Factoring Polynomials Over Local Fields
Factoring Polynomials Over Local Fields
โœ Sebastian Pauli ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 361 KB

We describe an efficient new algorithm for factoring a polynomial ฮฆ(x) over a field k that is complete with respect to a discrete prime divisor. For every irreducible factor ฯ•(x) of ฮฆ(x) this algorithm returns an integral basis for k[x]/ฯ•(x)k[x] over k.

Factoring Polynomials and the Knapsack P
Factoring Polynomials and the Knapsack Problem
โœ Mark van Hoeij ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 222 KB

For several decades the standard algorithm for factoring polynomials f with rational coefficients has been the Berlekamp-Zassenhaus algorithm. The complexity of this algorithm depends exponentially on n, where n is the number of modular factors of f . This exponential time complexity is due to a com