snarkify/sirius

feat(nifs): `compute_K`

cyphersnake opened this issue · 0 comments

$G(X)=F(\alpha)L_0(X)+K(X)Z(X)$

To evaluate of K(X) over dk+1 points: Minus $F(\alpha)L_0(X)$ has cost $O((dk+1)k)$, divide by Z(X) has cost $O((dk+1)k)$

Then do NTT with cost $O(dk\log(dk))$. i.e. total cost is $O(dk^2)+O(dk\log(dk))$.