Open cyphersnake opened 1 month ago
$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))$.
$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))$.