<p>Say I am given <span class="math-container">$n$</span> points <span class="math-container">$y_1, …, y_n$</span> in a finite field, and want to check whether they lie on a polynomial <span class="math-container">$f$</span> of degree <span class="math-container">$t &lt; n-1$</span> with <span class="math-container">$f(i)=y_i$</span>. The obvious way to do this is to interpolate a degree-<span class="math-container">$t$</span> polynomial through the first <span class="math-container">$t+1$</span> points, and then evaluate that polynomial on the remaining <span class="math-container">$n-t-1$</span> points. Is anything better possible?</p>
<p>I looked a bit at the property testing literature, but they typically assume that the evaluation of some function on the entire field is available (which is not the case here). They also tend to measure efficiency by queries to an oracle for the function, whereas I am more interested in the overall number of field multiplications/inversions performed.</p>

CC BY-SA 4.0
2023-03-27T12:15:33.033Z
What complexity do you have in mind? The approach you mention has quasi-linear complexity $O(\mathsf M(n)\log n)$. You want to remove log factors? 

Note that if $t \ll n$, you can do slightly better: First interpolation and multipoint evaluation on arithmetic progressions is faster than on arbitrary points (in $\mathsf M(n)\log n + O(\mathsf M(n))$ (*cf.* [Bostan & Schost](https://doi.org/10.1016/j.jco.2004.09.009)); Second, you can do $(n-t)/t$ degree-$t$ multipoint evaluations, so your overall complexity becomes $\frac{n}{t}\mathsf M(t)\log t + O(\mathsf M(n))$.
Bruno
CC BY-SA 4.0
2023-07-28T17:10:51.660Z
I want to do concretely better for $n\leq 100$. So saving constant factors may be better than saving log factors asymptotically.
user6584
<polynomials><property-testing>
Efficiently checking that points lie on a polynomial
user6584
# Efficiently checking that points lie on a polynomial

(Asked by: username_0 on 2023-03-27)

Say I am given $n$ points $y\_1, …, y\_n$ in a finite field, and want to check whether they lie on a polynomial $f$ of degree $t < n-1$ with $f(i)=y\_i$. The obvious way to do this is to interpolate a degree-$t$ polynomial through the first $t+1$ points, and then evaluate that polynomial on the remaining $n-t-1$ points. Is anything better possible?

I looked a bit at the property testing literature, but they typically assume that the evaluation of some function on the entire field is available (which is not the case here). They also tend to measure efficiency by queries to an oracle for the function, whereas I am more interested in the overall number of field multiplications/inversions performed.

**Tags:** polynomials, property-testing

> **Comments:**
> **username_1**: What complexity do you have in mind? The approach you mention has quasi-linear complexity $O(\mathsf M(n)\log n)$. You want to remove log factors?   Note that if $t \ll n$, you can do slightly better: First interpolation and multipoint evaluation on arithmetic progressions is faster than on arbitrary points (in $\mathsf M(n)\log n + O(\mathsf M(n))$ (*cf.* [Bostan & Schost](https://doi.org/10.1016/j.jco.2004.09.009)); Second, you can do $(n-t)/t$ degree-$t$ multipoint evaluations, so your overall complexity becomes $\frac{n}{t}\mathsf M(t)\log t + O(\mathsf M(n))$.  
> **username_0**: I want to do concretely better for $n\leq 100$. So saving constant factors may be better than saving log factors asymptotically.  

---

## 0 answers

