Computing Sparse Multiples of Polynomials |
| |
Authors: | Mark Giesbrecht Daniel S Roche Hrushikesh Tilak |
| |
Affiliation: | 1. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada 2. United States Naval Academy, Annapolis, MD, USA
|
| |
Abstract: | We consider the problem of finding a sparse multiple of a polynomial. Given f??Fx] of degree d over a field F, and a desired sparsity t, our goal is to determine if there exists a multiple h??Fx] of f such that h has at most t non-zero terms, and if so, to find such an h. When F=? and t is constant, we give an algorithm which requires polynomial-time 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|