scientific article; zbMATH DE number 3997161

From MaRDI portal
Publication:4723297





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.]











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4723297)