Hello, I am trying to understand how and why we change from COEFF to EVAL format and vice-versa. Is there any paper basis explaining it?
Thank you
Hello,
Its to speed up the polynomial multiplications. In COEFF space you have a complexity O(N^2) and in EVAL a complexity O(nlogn).
In can’t think of a paper, but here is a blog that has a good explanation for something similar (digital signature) (link).
Or may be a paper that explains the implementation: A note on the implementation of the Number
Theoretic Transform - Michael Scott (link)
You can see there that the way to change from COEFF to EVAL is using Number Theoretic Transform (NTT), and then from EVAL to COEFF is using the inverse of this INTT. Basically is a Fourier transform for finite fields.