Computer Science – Symbolic Computation
Scientific paper
2010-09-16
Computer Science
Symbolic Computation
Extended abstract appears in Proc. ISAAC 2010, pp. 266-278, LNCS 6506
Scientific paper
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.
Giesbrecht Mark
Roche Daniel S.
Tilak Hrushikesh
No associations
LandOfFree
Computing sparse multiples of polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computing sparse multiples of polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing sparse multiples of polynomials will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-27957