Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Factoring Multivariate Polynomials with Many Factors and Huge Coefficients
verfasst von : Michael Monagan, Baris Tuncer
Erschienen in: Computer Algebra in Scientific Computing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The standard approach to factor a multivariate polynomial in \(\mathbb {Z}[x_{1},x_{2},\dots ,x_{n}]\) is to factor a univariate image in \(\mathbb {Z}[x_{1}]\) then recover the multivariate factors from their images using a process known as multivariate Hensel lifting. For the case when the factors are expected to be sparse, at CASC 2016, we introduced a new approach which uses sparse polynomial interpolation to solve the multivariate polynomial diophantine equations that arise inside Hensel lifting.
In this work we extend our previous work to the case when the number of factors to be computed is more than 2. Secondly, for the case where the integer coefficients of the factors are large we develop an efficient p-adic method. We will argue that the probabilistic sparse interpolation method introduced by us provides new options to speed up the factorization for these two cases. Finally we present some experimental data comparing our new methods with previous methods.