I'm trying to implement a cryptographic scheme that leverages constant-sized polynomial commitments by Kate et al .
I'm looking for a library that can interpolate a polynomial fast via FFT in a finite field, but from values at arbitrary points (i.e., not roots of unity). A technique for doing this in
O(n log^2(n)) time for
n points is described in "Fast evaluation and interpolation," by
H. T. Kung.
I'm aware of:
...but AFAICT none of them seem to support interpolation from values at arbitrary points.