Polynomial factorization: Sharp bounds, efficient algorithms (Q689110)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Polynomial factorization: Sharp bounds, efficient algorithms |
scientific article |
Statements
Polynomial factorization: Sharp bounds, efficient algorithms (English)
0 references
16 December 1993
0 references
The paper shows that, in order to realize fast algorithms, it is necessary to control the size of the coefficients in one irreducible factor. A bound on this size is presented in Theorem 1. It makes use of the weighted norm and it is almost optimal. The paper shows how to use this bound in the process of \(p\)-adic lifting in such a way to obtain an efficient algorithm. A worked example completes the paper.
0 references
polynomial factorization
0 references
\(p\)-adic lifting
0 references
efficient algorithm
0 references
