Paper Info
Title
Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields
Abstract
We present algorithms that compute all irreducible factors of degree ≤ d of supersparse (lacunary) multivariate polynomials in n variables over an algebraic number field in deterministic polynomial-time in (l+d)n, where l is the size of the input polynomial. In supersparse polynomials, the term degrees enter logarithmically as their numbers of binary digits into the size measure l. The factors are again represented as supersparse polynomials. If the factors are represented as straight-line programs or black box polynomials, we can achieve randomized polynomial-time in (l+d)O(1). Our approach follows that by H. W. Lenstra, Jr., on computing factors of univariate supersparse polynomials over algebraic number fields. We generalize our ISSAC 2005 results for computing linear factors of supersparse bivariate polynomials over the rational numbers by appealing to recent lower bounds on the height of algebraic numbers and to a special case of the former Lang conjecture.
Year
DOI
Venue
2006
10.1145/1145768.1145798
ISSAC
Keywords
Field
DocType
supersparse bivariate polynomial,randomized polynomial-time,deterministic polynomial-time,small degree factor,h. w. lenstra,algebraic number field,supersparse polynomial,size measure l,multivariate supersparse,rational number,univariate supersparse polynomial,algebraic number,polynomial factorization,lower bound,height,algebraic numbers,polynomial time
Wilson polynomials,Discrete mathematics,Combinatorics,Classical orthogonal polynomials,Orthogonal polynomials,Macdonald polynomials,Gegenbauer polynomials,Discrete orthogonal polynomials,Hahn polynomials,Difference polynomials,Mathematics
Conference
ISBN
Citations 
PageRank 
1-59593-276-3
18
0.77
References 
Authors
12
2
Name
Order
Citations
PageRank
Erich Kaltofen12332261.40
Pascal Koiran2919113.85