<p><strong>Setup.</strong> Let <span class="math-container">$\mathbb{F}$</span> be a finite field with a multiplicative subgroup <span class="math-container">$E = \{e_1, \dots, e_k\}$</span> of order <span class="math-container">$k$</span>. Given a list <span class="math-container">$y = y_1, \dots, y_k\in \mathbb{F}$</span> let <span class="math-container">$p$</span> be the unique polynomial of degree <span class="math-container">$k-1$</span> s.t. <span class="math-container">$p(e_i) = y_i$</span> for all <span class="math-container">$i\in [k]$</span>.
Let <span class="math-container">$E'=\{e'_1, \dots, e'_t\}\not\subset E$</span> be a additive coset of a subgroup of <span class="math-container">$E$</span> (i.e. <span class="math-container">$t &lt; k$</span>).</p>
<p><strong>Problem.</strong> Given <span class="math-container">$y$</span> as input, can we compute <span class="math-container">$p(e'_i)$</span> for all <span class="math-container">$i\in [t]$</span> in time <span class="math-container">$O_{\log|\mathbb{F}|}(k + t\;\mathrm{polylog}\;k)$</span>? That is, if <span class="math-container">$t = k / \mathrm{polylog}(k)$</span>, the computation would run in time <span class="math-container">$O_{\log|\mathbb{F}|}(k)$</span>. Note that if <span class="math-container">$t = O(k)$</span>, FFT solves this problem in time <span class="math-container">$O_{\log|\mathbb{F}|}(k + k \;\mathrm{polylog}\; k) = O(k \;\mathrm{polylog}\; k)$</span>.</p>
<p><strong>Relaxation.</strong> It would be still be interesting to solve this problem over any finite field <span class="math-container">$\mathbb{F}$</span> and any (disjoint) subsets <span class="math-container">$E,E'\subset \mathbb{F}$</span> of size <span class="math-container">$k,t$</span>, respectively, in time <span class="math-container">$O_{\log|\mathbb{F}|}(k\log\log k + t\;\mathrm{polylog}\;k)$</span>.</p>

CC BY-SA 4.0
2024-07-12T14:02:11.730Z
What is $n$? Is it the size of $$?
Bruno
CC BY-SA 4.0
2024-07-13T20:08:21.067Z
@Bruno Sorry, $n$ was supposed to be $k$. I updated the question to reflect that -- thanks!
Matan Shtepel
CC BY-SA 4.0
2024-07-14T11:27:34.273Z
Perhaps you can compute $p \pmod{(x-e_1')(x-e_2')\cdots}$?
Command Master
CC BY-SA 4.0
2024-07-15T02:27:04.867Z
Thanks for the suggestion @CommandMaster! I agree finding $r = p \mod \prod_{i\in t}(x - e_i')$, and evaluating $r$ on $E'$ (in time $t\mathrm{polylog} \;t)$ is a valid approach. However, it is not clear to me how to find $r$ within the requested time bound. 

One can find the remainder of a degree $k$ polynomial by a degree $O(k)$ polynomial in time $O(k\mathrm{polylog} k)$ using [Sieveking-Kung division])(https://people.csail.mit.edu/madhu/ST12/scribe/lect06.pdf), but that does not meet our time bound. Not clear how to optimize for reducing by a smaller degree $t$ polynomial.
Matan Shtepel
<polynomials><algebra><fft>
Multipoint evaluation in Lagrange basis
Matan Shtepel
# Multipoint evaluation in Lagrange basis

(Asked by: username_0 on 2024-07-11)

**Setup.** Let $\mathbb{F}$ be a finite field with a multiplicative subgroup $E = \{e\_1, \dots, e\_k\}$ of order $k$. Given a list $y = y\_1, \dots, y\_k\in \mathbb{F}$ let $p$ be the unique polynomial of degree $k-1$ s.t. $p(e\_i) = y\_i$ for all $i\in [k]$.
Let $E'=\{e'\_1, \dots, e'\_t\}\not\subset E$ be a additive coset of a subgroup of $E$ (i.e. $t < k$).

**Problem.** Given $y$ as input, can we compute $p(e'\_i)$ for all $i\in [t]$ in time $O\_{\log|\mathbb{F}|}(k + t\;\mathrm{polylog}\;k)$? That is, if $t = k / \mathrm{polylog}(k)$, the computation would run in time $O\_{\log|\mathbb{F}|}(k)$. Note that if $t = O(k)$, FFT solves this problem in time $O\_{\log|\mathbb{F}|}(k + k \;\mathrm{polylog}\; k) = O(k \;\mathrm{polylog}\; k)$.

**Relaxation.** It would be still be interesting to solve this problem over any finite field $\mathbb{F}$ and any (disjoint) subsets $E,E'\subset \mathbb{F}$ of size $k,t$, respectively, in time $O\_{\log|\mathbb{F}|}(k\log\log k + t\;\mathrm{polylog}\;k)$.

**Tags:** polynomials, algebra, fft
> **Comments:**
> **username_1**: What is $n$? Is it the size of $$?  
> **username_0**: @Bruno Sorry, $n$ was supposed to be $k$. I updated the question to reflect that -- thanks!  
> **username_2**: Perhaps you can compute $p \pmod{(x-e_1')(x-e_2')\cdots}$?  
> **username_0**: Thanks for the suggestion @CommandMaster! I agree finding $r = p \mod \prod_{i\in t}(x - e_i')$, and evaluating $r$ on $E'$ (in time $t\mathrm{polylog} \;t)$ is a valid approach. However, it is not clear to me how to find $r$ within the requested time bound.   One can find the remainder of a degree $k$ polynomial by a degree $O(k)$ polynomial in time $O(k\mathrm{polylog} k)$ using [Sieveking-Kung division])(https://people.csail.mit.edu/madhu/ST12/scribe/lect06.pdf), but that does not meet our time bound. Not clear how to optimize for reducing by a smaller degree $t$ polynomial.  

---

## 0 answers

