Computing the multilinear factors of lacunary polynomials without heights

DOI10.1016/j.jsc.2020.04.013zbMath1481.11105arXiv1311.5694OpenAlexW3022243219MaRDI QIDQ2229711

Pascal Koiran, Yann Strozecki, Arkadev Chattopadhyay, Bruno Grenet, Natacha Portier

Publication date: 18 February 2021

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.5694

zbMATH Keywords

finite fieldspolynomial factorizationnumber fieldspolynomial-time complexityWronskian determinantmultivariate lacunary polynomials

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Polynomials (irreducibility, etc.) (11R09) Factorization (11Y05)

Uses Software

• Lacunaryx

Cites Work

• A Wronskian approach to the real \(\tau\)-conjecture
• Detecting lacunary perfect powers and computing their roots
• Counting curves and their projections
• New recombination algorithms for bivariate polynomial factorization based on Hensel lifting
• Deterministically testing sparse polynomial identities of unbounded degree
• Algorithm of polynomial complexity for factoring polynomials over local fields
• Sparse complex polynomials and polynomial reducibility
• A polynomial time algorithm for diophantine equations in one variable
• Sparse shifts for univariate polynomials
• Overdetermined systems of sparse polynomial equations
• Bounded-degree factors of lacunary multivariate polynomials
• Handbook of Finite Fields
• Modern Computer Algebra
• Faster real feasibility via circuit discriminants
• Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields
• Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields
• Factoring bivariate lacunary polynomials without heights
• Wronskians and Linear Independence
• Irreducibility and greatest common divisor algorithms for sparse polynomials
• Computing low-degree factors of lacunary polynomials
• Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
• Practical polynomial factoring in polynomial time
• Supersparse black box rational function interpolation
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• On the complexity of factoring bivariate supersparse (Lacunary) polynomials
• Lacunaryx
• On lacunary polynomial perfect powers
• Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Computing the multilinear factors of lacunary polynomials without heights