Consider using Fast Fourier Transform for polynomial interpolation.

[afck]

We're currently doing polynomial interpolation the naive way, which is O(n²). With Fast Fourier Transform (FFT), it should be possible in O(n log(n)). We should try to estimate the actual count of arithmetic operations first, to make sure it's worth doing this in practice, and for all network sizes.

http://dcn.icc.spbstu.ru/~petert/papers/fftEng.pdf
http://web.cecs.pdx.edu/~maier/cs584/Lectures/lect07b-11-MG.pdf

[afck]

Sorry, wrong crate: threshold cryptography has been moved out of hbbft. I created a new issue: poanetwork/threshold_crypto#13