Geometric Factorization in ℤ[????]: A Graded Newton Polytope Algorithm for Multivariate Polynomial Decomposition

Abstract

This paper introduces the Graded Newton Filtration Algorithm (GNFA), a novel, deterministic, and geometrically grounded method for the exact factorization of multivariate polynomials with integer coefficients. The inherent computational difficulty of distinguishing prime (irreducible) from composite (reducible) factors in  has  long been dominated by classical algorithms like Zassenhaus, which suffer from exponential complexity due to combinatorial subset enumeration, and the LLL algorithm, which, while theoretically polynomial-time, is impractical due to large constants and numerical instability. GNFA essentially sidesteps these bottlenecks, by using the combinatorial geometry of the Newton polytope of the polynomial. The algorithm defines a graded ring structure on and encodes the global factorization problem in terms of local factorizations over the faces of through face valuations. Then, these local factors are such raised to a global divisor by LLL in fashion ensured by a Hensel- type lifting theorem in the associated graded ring. Under the Extended Riemann Hypothesis (ERH), GNFA enjoys a quasi-linear expected running time of, where is the number of non-zero terms, is the degree, \(d\) is the number of variables and bounds the coefficient bit-length a significant asymptotic improvement over all previous deterministic approaches. Extensive experimental comparison against state-of-the-art systems (Magma and SageMath) shows GNFA’s practical superiority by more than two orders of magnitude for benchmark classes including sparse polynomials, Vandermonde determinants, and Swinnerton-Dyer polynomials. The algorithm’s impact extends to critical applications: in post-quantum cryptography, it provides an efficient tool for certifying the irreducibility of Ring-LWE modulus polynomials; in algebraic coding theory, it facilitates the construction and cryptanalysis of Goppa codes. This work thus establishes a new geometric paradigm for polynomial factorization, setting a higher standard for exact computation in polynomial rings over the integers.