Computing sparse multiples of polynomials

complexity;polynomial;sparse;multiple;algorithm;lowerbound;Computer Science

Tilak, Hrushikesh

University of Waterloo

关键词: complexity;    polynomial;    sparse;    multiple;    algorithm;    lowerbound;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/5455/1/spmul.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

We consider the problem of finding a sparse multiple of a polynomial. Givena polynomial f ∈ F[x] of degree d over a field F, and a desired sparsityt = O(1), our goal is to determine if there exists a multiple h ∈ F[x] of fsuch that h has at most t non-zero terms, and if so, to find such an h.When F = Q, we give a polynomial-time algorithm in d and the size ofcoefficients in h. For finding binomial multiples we prove a polynomial boundon the degree of the least degree binomial multiple independent of coefficientsize.When F is a finite field, we show that the problem is at least as hard asdetermining the multiplicative order of elements in an extension field of F(a problem thought to have complexity similar to that of factoring integers),and this lower bound is tight when t = 2.