We consider the problem of finding a sparse multiple of a polynomial. Given
`f`
in **F**[`x`] of degree `d` over a field **F**, and a desired
sparsity `t`, our goal is to
determine if there exists a multiple `h` in **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** and
`t` is constant, we
give a polynomial-time algorithm in `d` and the size of
coefficients in `h`. 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.