Some of the details about FFTs in implementation_details.rst are incorrect

[j2kun]

Hi there! I was reading this doc and I found it helpful, but it had two mistakes about FFTs I thought you might want to correct. Note I did not study the NTT section in detail. Please let me know if you spot any errors in my corrections.

Factor of 2 error in naive approach

The doc states

This way the regular convolution of these extended arrays will result in the negacyclic convolution of original arrays.

I believe it should be 2 times the negacyclic convolution. A demonstration shows that we have to halve the output post ifft to make it correct: https://gist.github.com/j2kun/4555ea100efc4b5f574e030623706cd8

Tangent FFT approach does not work

Demo implementation of the algorithm described in the doc: https://gist.github.com/j2kun/49a52731e05f3247ab6f9519ac193aa3

It seems the correct approach is given (in less detail) by https://math.stackexchange.com/a/1445170, which differs from the nufhe doc by applying a different initial mapping (adding instead of subtracting), removing the conjugation step post ifft, and inverting the twist post ifft instead of applying a second twist by the root of unity.

Corrected implementation: https://gist.github.com/j2kun/874ce05ae956611cb91dd8822c34d1de

[fjarri]

Thanks for the feedback!

Factor of 2 error in naive approach

I wouldn't call it a mistake, given that we're not particularly interested in the naive method, and no formulas were provided, "up to a constant factor" was implied. But I agree, no harm in being precise.

Tangent FFT approach does not work

I believe you have a mistake in your code: your primitive root is set to exp(2pi * 1j/n), while in the docs it's exp(-2pi * 1j/n). If I make that change the results seem to match the reference. Could you verify?