Faster compuation of permutation polynomials

[dtebbs]

The current Plonk implementation enumerates the entire set $H' = H \cup k_1 \cdot H \cup k_2 \cdot H$, permutes the set, and then does an iFFT to compute the permutation polynomials (See srs.tcc and related comments).

@vesselinux I think instead we can compute the differences between, say $S_{\sigma_1} - S_{ID_1} = S_{\sigma_1}(X) - X$ as an array of values in the evaluation space. For each $i$ we want to subtract $\omega^i L_i(X)$ from $S_{ID_1}$ (to get a zero at $\omega^i$) and add $\sigma^{\star}(j) L_i(X)$. Therefore, if we create an array with $i$-th entry as $\omega^i - \sigma^{\star}(i)$ (which only needs to be computed for entries which are actually affected by the permutation) we can take the iFFT of this to get $S_{\sigma_1} - S_{ID_1}$. Adding a $1$ in the $X$ position (index 1) should then yield $S_{\sigma_1}$.

For $S_{\sigma_2}$ and $S_{\sigma_3}$ we need to use $k_1$ and $k_2$ instead of $1$ at the end.

I may have missed some detail here, but I think we can use this as an approach to avoid having to enumerate the entire set $H'$ and manually permute it.