# Sparse Polynomial Interpolation

Monagan, Michael

### Abstract

We consider the problem of interpolating a sparse multivariate polynomial

*TeX Embedding failed!* of degree *TeX Embedding failed!* with *TeX Embedding failed!* non-zero terms over a ring.

Newton interpolation needs *TeX Embedding failed!* points to interpolate *TeX Embedding failed!* which is

exponential in *TeX Embedding failed!*. Our goal is an algorithm whose time complexity

is polynomial in *TeX Embedding failed!*, *TeX Embedding failed!* and *TeX Embedding failed!*. Our motivation is polynomial GCD computation.

Here one normally works modulo a prime *TeX Embedding failed!* and hence interpolates

over the ring of integers modulo *TeX Embedding failed!*.

In the talk we will present Ben-Or and Tiwari's algorithm from 1988 for

interpolation over the integers. Many authors have tried to modify

this algorithm to interpolate over finite fields. We present one beautiful

modification by Huang and Rao and then our own attempt which we have

implemented and parallelized. Currently we are trying another approach

which assumes the characteristic *TeX Embedding failed!* is *TeX Embedding failed!* and also that *TeX Embedding failed!* is "smooth" so

that discrete logarithms in *TeX Embedding failed!* are efficient.

### Details

- ‹ previous
- 46 of 62
- next ›