arXiv Open Access 2023

Factoring sparse polynomials fast

Alexander Demin Joris van der Hoeven

Lihat Sumber

Abstrak

Consider a sparse polynomial in several variables given explicitly as a sum of non-zero terms with coefficients in an effective field. In this paper, we present several algorithms for factoring such polynomials and related tasks (such as gcd computation, square-free factorization, content-free factorization, and root extraction). Our methods are all based on sparse interpolation, but follow two main lines of attack: iteration on the number of variables and more direct reductions to the univariate or bivariate case. We present detailed probabilistic complexity bounds in terms of the complexity of sparse interpolation and evaluation.

Topik & Kata Kunci

cs.SC math.AC

Penulis (2)

Alexander Demin

Joris van der Hoeven

Format Sitasi

APA MLA BibTeX

Demin, A., Hoeven, J.v.d. (2023). Factoring sparse polynomials fast. https://arxiv.org/abs/2312.17380

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2023
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓