No label defined (Q4723297)
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 3997161
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3997161 |
Statements
1986
0 references
dense polynomials
0 references
polynomial factorization
0 references
lifting process
0 references
0.91482043
0 references
0.91391486
0 references
0.90838397
0 references
0 references
0.90400183
0 references
0.9023468
0 references
0.8988119
0 references
0.8980205
0 references
Nowadays, the problem of factoring polynomials is known to be a polynomial-time problem, due to the work of Lenstra, but his algorithms are not efficient enough to supersede the classical ones. A lot of work is done to improve them, but from a practical point of view, it is still worthy to improve the classical algorithm, and this work belongs to this kind of improvements. The polynomials to factor are dense polynomials. In univariate polynomial factorization, the early detection of the true factors usually spares a lot of computation time. Here a refinement of the lifting process presented earlier by the author [Lect. Notes Comput. Sci. 174, 297--309 (1984; Zbl 0595.68041)] is given and discussed. This lifting allows a test for the early detection of the true factors as in the univariate case. Moreover, the reduction of the number of lifting steps reduces the worst-case complexity of the reconstruction step and reduces the time required by the factorization process. The method to compute the homogeneous parts has refined, and a new one based on the Taylor's expansion is presented. [For the entire collection see Zbl 0591.00035.]
0 references