Fast computation of Bézout polynomials

(Alex Ozdemir)

Let $\mathbb{F}$ be a field (in practice, a finite field of prime order). Let $a_1, \ldots, a_m$ be $m$ distinct elements of $\mathbb{F}$. Let $z(X) = \prod_{i=1}^m (X - a_i).$ Then (since the roots $a_i$ are distinct) $z$ and its derivative $z'$ have no common factor, so there exist polynomials $s(X)$ and $t(X)$ such that $sz + tz' = 1$.

Is there an algorithm to compute the coefficients of $s$ and $t$, from $a_1, \ldots, a_m$, using at most $O(m \log m)$ field operations?

Motivation

Say that a verifier $V$ has $m$ values $a_1, \ldots , a_m$ in a large prime field $\mathbb{F}$, and that a prover $P$ wants to convince $V$ that the $a_i$’s are all distinct. But, $V$ can only do sampling, addition, multiplication, and equality testing in $\mathbb{F}$ (and each of these operations has unit cost). $V$ can assert $O(m^2)$ disequalities to establish distinctness, but this is very expensive. Another option is for $P$ and $V$ to both define a polynomial $z(X) = \prod_i (X - a_i)$, and then for $P$ to convince $V$ that $z$ and $z'$ (its derivative) share no roots. $P$ can do this by sending polynomials $s$ and $t$ (in coefficient form) to $V$. $V$ wants to check that $zs + z't = 1$ (as polynomials), which it can do (with high probability) by sampling a random $y$ in $\mathbb{F}$ and checking $z(y)s(y) + z'(y)t(y) = 1$. $V$ can test this with only $O(m)$operations!

But now, $P$ has to compute the coefficients for $s$ and $t$. Is it possible for $P$ to do this in $O(m \log m)$ time? This would be nice, because in many zkSNARKs, $P$ already takes $O(m \log m)$ time, for other reasons.

The best known approaches either interpolate $t$ or use the fast extended euclidean algorithm, both of which take $O(m \log^2 m)$ time.

This problem (and related ones) are important in memory-checking for zkSNARKs 1. For the related problems, see 1. One related problem that is not in 1 is negated lookup arguments, where P argues that some values $v_1, \ldots, v_n$ are all not in a set $a_1, \ldots, a_m$.