We consider the problem of finding a sparse multiple of a polynomial. Given
a polynomial f ∈ F[x] of degree d over a field F, and a desired sparsity
t = O(1), our goal is to determine if there exists a multiple h ∈ F[x] of f
such 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 of
coefficients in h. For finding binomial multiples we prove a polynomial bound
on the degree of the least degree binomial multiple independent of coefficient
size.
When F is a finite field, we show that the problem is at least as hard as
determining 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.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/5455 |
| Date | 20 August 2010 |
| Creators | Tilak, Hrushikesh |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0019 seconds