Extracting sparse factors from multivariate integral polynomials (Q1940925)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Extracting sparse factors from multivariate integral polynomials |
scientific article; zbMATH DE number 6143066
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Extracting sparse factors from multivariate integral polynomials |
scientific article; zbMATH DE number 6143066 |
Statements
Extracting sparse factors from multivariate integral polynomials (English)
0 references
11 March 2013
0 references
A algorithm for the following problem is presented. Given a sparse multivariate polynomial in several variables over the integers, and a bound \(t\), find all factors with at most \(t\) terms. The algorithm is probabilistic with expected polynomial time in \(t\), the number of variables, the height of the coefficients, the number of terms of the polynomial, and the degree of the polynomial.
0 references
polynomial factorization
0 references
discrete logarithm
0 references
sparse polynomial
0 references
