TOPICS
Search

Landau-Mignotte Bound


The Landau-Mignotte bound, also known as the Mignotte bound, is used in univariate polynomial factorization to determine the number of Hensel lifting steps needed. It gives an upper bound for the absolute value of coefficients of any nontrivial factor of a polynomial P(x) in Z[x].

The bound is given by

 B=(d-1; |_1/2d_|-1)+(d-1; |_1/2d_|)||P||_2,

where ||P||_2 is the 2-norm and

 d=|_1/2deg(P)_|.

Factorization over the integers is done by factoring the polynomial modulo a "good" prime p using the Berlekamp-Zassenhaus algorithm, and the irreducible factors are then lifted to ones modulo p^k. There are guidelines for choosing p. For example, p should not evenly divide the leading coefficient of the polynomial, and mod(P,p) should be squarefree.


See also

Hensel Lifting

This entry contributed by Bhuvanesh Bhatt

Explore with Wolfram|Alpha

References

van Hoeij, M. "Factoring Polynomials and the Knapsack Problem." J. Number Th. 95, 167-189, 2002.

Referenced on Wolfram|Alpha

Landau-Mignotte Bound

Cite this as:

Bhatt, Bhuvanesh. "Landau-Mignotte Bound." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/Landau-MignotteBound.html

Subject classifications