Computing the multilinear factors of lacunary polynomials without heights

作     者：Chattopadhyay, Arkadev Grenet, Bruno Koiran, Pascal Portier, Natacha Strozecki, Yann 

作者机构：Tata Inst Fundamental Res Sch Technol & Comp Sci Mumbai Maharashtra India Univ Montpellier CNRS LIRMM Montpellier France Univ Lyon CNRS EnsL UCBLLIP Lyon 07 France Univ Versailles St Quentin DAVID Lab Versailles France 

出 版 物：《JOURNAL OF SYMBOLIC COMPUTATION》 (符号计算杂志)

年 卷 期：2021年第104卷

页      面：183-206页

核心收录：

学科分类：08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Multivariate lacunary polynomials Polynomial factorization Polynomial-time complexity Number fields Finite fields Wronskian determinant 

摘      要：We present a deterministic algorithm which computes the multilinear factors of multivariate lacunary polynomials over number fields. Its complexity is polynomial in l(n) where l is the lacunary size of the input polynomial and nits number of variables, that is in particular polynomial in the logarithm of its degree. We also provide a randomized algorithm for the same problem of complexity polynomial in l and n. Over other fields of characteristic zero and finite fields of large characteristic, our algorithms compute the multilinear factors having at least three monomials of multivariate polynomials. Lower bounds are provided to explain the limitations of our algorithm. As a by-product, we also design polynomial-time deterministic polynomial identity tests for families of polynomials which were not known to admit any. Our results are based on so-called Gap Theorem which reduce high-degree factorization to repeated low-degree factorizations. While previous algorithms used Gap Theorems expressed in terms of the heights of the coefficients, our Gap Theorems only depend on the exponents of the polynomials. This makes our algorithms more elementary and general, and faster in most cases. (C) 2020 Elsevier Ltd. All rights reserved.