Factorisation of polynomials
The problem of factoring polynomials over finite fields and over the integers is considered. Factoring polynomials over an arbitrary finite field is first described using Berlekamp's algorithm. An improvement of this algorithm is given in section 3, where two irreducibility tests are also described. The next three sections of the paper consider factorization of polynomials over \({\mathbb Z}\). It is observed that if \(P \in {\mathbb Z} [X]\) then it factors in \({\mathbb Z}[X]\). The use of Hensel lifting to relate the factorization of a polynomial in \({\mathbb Z}[X]\) modulo a prime \(p\) to its factorization in \({\mathbb Z}[X]\) is discussed, and a factorization based on these observations is given. An algorithm for factoring polynomials with integer coefficients in \({\mathbb Z}[X]\) using the LLL lattice reduction technique is then described. Finally an algorithm to factor a polynomial \(A \in K[X]\) over the algebraic number field \(K[X]\) is given. For the entire collection see Zbl 0924.13021.
- On polynomial factorization
- Algorithms related to the decomposition of polynomials
- A fast algorithm for polynomial factorization over \(\mathbb Q_p\)
- Factorisation patterns of division polynomials
- Efficiently factoring polynomials modulo \(p^4\)
- A note on Gröbner bases and Berlekamp's algorithm
- Polynomial factorization algorithms over number fields
- scientific article; zbMATH DE number 3860385 (Why is no real title available?)
- Factorization of polynomials over finite fields and decomposition of primes in algebraic number fields
- Factorisation sur $\mathbb {Z}[X]$ des polynômes de degré élevé à l’aide d’un monomorphisme
- scientific article; zbMATH DE number 4165010 (Why is no real title available?)
- A remark on factorisation
- scientific article; zbMATH DE number 4002212 (Why is no real title available?)
- scientific article; zbMATH DE number 4069018 (Why is no real title available?)
- scientific article; zbMATH DE number 1960426 (Why is no real title available?)
- Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields
- Factoring polynomials via polytopes
- scientific article; zbMATH DE number 1857497 (Why is no real title available?)
- scientific article; zbMATH DE number 922258 (Why is no real title available?)
- On the factors of a polynomial
- The van Hoeij algorithm for factoring polynomials
- Newton polygons of higher order in algebraic number theory
- The use of finite polynomial rings in the factorization of the general polynomial
- Modular Las Vegas algorithms for polynomial absolute factorization
- Factoring polynomials and the knapsack problem
This page was built for publication: Factorisation of polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4238960)
