Factorisation of polynomials (Q4238960)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1276815
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Factorisation of polynomials |
scientific article; zbMATH DE number 1276815 |
Statements
20 April 1999
0 references
factoring polynomials over finite fields
0 references
Berlekamp's algorithm
0 references
Hensel lifting
0 references
algorithm
0 references
factoring polynomials with integer coefficients
0 references
LLL lattice reduction
0 references
algebraic number field
0 references
Factorisation of polynomials (English)
0 references
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.
0 references