# Computing cached quotients over a coset

In the Lemma 3.1 from $\mathfrak{cq}$ paper (https://eprint.iacr.org/2022/1763.pdf), it is shown how we can compute KZG commitments to $Q_i(X)$ polynomials in $\mathcal{O}(N\log(N))$. The algorithm relies on a subgroup $\mathbb{V}\subset\mathbb{F}$ of size $N$. In particular, its vanishing polynomial $Z_{\mathbb{V}}(X)$ and Lagrange base $\{L_i(X)\}_{i\in[N]}$ are used. We want to show that the complexity is preserved if we use arbitrary coset in place of $\mathbb{V}$.

*Note: We overload 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.*

## Coset

Let us redefine $\mathbb{V}$ as $\{a·g^k\}_{k\in[N]}$, where $a$ is an arbitrary, non-zero field element and $g$ is an $N$th root of unity in the field.

## Lagrange base

For $i\in[N]$ we denote by $L_i(X)$ the $i$th Lagrange polynomial of $\mathbb{V}$:
$$
L_i(X) = \frac{Z_\mathbb{V}(X)}{Z'_\mathbb{V}(a·g^i)(X-a·g^i)}
$$
where
$$
Z_\mathbb{V}(X) = \prod_{j\in[N]}(X-a·g^j)
$$
and
$$
Z'_\mathbb{V}(a·g^i) = \prod_{j\in[N], j\neq i}(a·g^i-a·g^j) \\= a^{N-1}·\prod_{j\in[N], j\neq i}(g^i-g^j)
$$

Now observe, that $Z_\mathbb{V}(X)$ can be simplified to $X^N - a^N$. This is because:
- both polynomials are of the same degree
- $\forall_{i\in[N]}\ (a·g^i)^N - a^N = a^N·g^{iN} - a^N = a^N - a^N = 0$: therefore the new polynomial has the same roots as the original one
- both polynomials have the same leading coefficient at $X^N$

## Quotient

We define $Q_i(X)$ as:
$$
Q_i(X) = Z'_\mathbb{V}(a·g^i)^{-1} · K_i(X)
$$

for $K_i(X) := \frac{T(X)-T(a·g^i)}{X - a·g^i}$. From https://hackmd.io/@pmikolajczyk41/fk-on-coset we know that in $\mathcal{O}(N\log(N))$ we can compute $\{[K_i(x)]\}_{i\in[N]}$, i.e. the KZG commitments to $K_i$ with the secret $x$.

Hence, in order to get KZG commitments to $\{Q_i(X)\}_{i\in[N]}$ it is sufficient to scale previous commitments by a corresponding scalar of $Z'_\mathbb{V}(a·g^i)^{-1}$. From the previous section, we can compute its value:
$$
Z'_{\mathbb{V}}(X) = N·X^{N-1} \implies Z'_{\mathbb{V}}(a·g^i)^{-1} = (N·a^{N-1}·g^{i(N-1)})^{-1} = (N·a^{N-1})^{-1} · g^{i}
$$
Hence, the new scaling requires computing $(N·a^{N-1})^{-1}$ factor, which can be done in $\mathcal{O}(\log(N))$ field multiplications. This clearly leads to the complexity preservation for the whole algorithm.