# Feist-Khovratovich algorithm for cosets

FK algorithm (https://eprint.iacr.org/2023/033.pdf) serves for fast (amortized) computation of KZG proofs over a subgroup. We want to show that it can be adapted for cosets, within the same time complexity, i.e. $\mathcal{O}((n+d)·\log(n+d))$, where $d$ denotes the maximum degree of the committed polynomial and $n$ denotes the size of the subgroup/coset.

## Notation

We inherit the notation and the setup from the original paper. In particular:
- $f(X)\in \mathbb{F}_{\leq d}$ is the polynomial that we commit to (with coordinates $(f_0, \dots, f_d)$)
- $\{[s^i]\}_{i\in\{0,1,\dots,d\}}$ is the output of the trusted setup
- $\{\xi_k\}_{k\in[n]} = \{a·g^k\}_{k\in[n]}$ is the evaluation domain: a coset of a subgroup $G$ with a generator $g$ with an offset $a$.

We have overloaded the notation of $[n]$ - depending on the context it will denote either the $n$th power of the KZG group's unity element or the set $\{1,\dots,n\}$. It will allways be unambiguous.

## FK algorithm

### Introducing polynomial $h$

Let us take some $y$ and let $z:=f(y)$. The first step of the algorithm is to consider polynomial $T(X) = \frac{f(X) - z}{X - y}$. Its coefficients can be easily computed based on $f$'s coefficients and $y$. It is therefore a polynomial over the variable $X$ with a parameter $y$. The trick is that we can reinterpret it as a polynomial over variable $y$ with a parameter $X$ -- this is the whole point of the regrouping the terms in section 2.1. From that, by setting $X$ to $[s]$ we get a universal polynomial $h$. This phase, especially computing its coefficient is completely independent of the evaluation domain and hence we get it in time $\mathcal{O}(d\log(d))$.

### Evaluating $h(X)$ on a coset

Given a polynomial $h(X) = \sum_{i\in\{0,\dots,d\}}h_i·X^i$ we want to evaluate it on a set $\{a·g^k\}_{k\in [n] }$. Notice that:
$$
\sum_{i\in\{0,\dots,d\}}h_i·(a·g^k)^i =
\sum_{i\in\{0,\dots,d\}}(h_i·a^i)·(g^k)^i
$$

Thus we can define a new polynomial $h'(X)$ with coefficients $h'_i := h_i · a^i$ and evaluate it directly on the subgroup $G$ using classical FFT procedure in time $\mathcal{O}(n\log(n))$. Observe that calculating coefficients $h'_i$ can be done with $\mathcal{O}(d)$ group multiplications ($h_i$ belong to the KZG group, $h'_i$ requires scaling $h_i$ by a scalar $a^i$, we can compute them ascending with $i$, thus accumulating $a_i$).