Hello, I’m digging into the NTT implementation in the library.
In the function NumberTheoreticTransformNat::ForwardTransformToBitReverseInPlace, I’m curious about what are the rootOfUnityTable and preconRootOfUnityTable for and the differences?
I have implemented my own NTT (through the DFT and FFT) and based on the same parameter(ex. N=1024, q=134215681, primitive root=282116^2 mod q), both can successfully take the NTT and INTT.
But compared to your NTT, I found that the NTT result is different (not just the “order” difference but the “value”), and I check the parameter set, which is N=1024, q=134215681, and GetRootOfUnity=282116.
Does anyone know what causes the different between them?
What algorithm you used to implement NTT? NTT can refer to several things, so it’s important to be clear about which definition you mean.
Note that OpenFHE implementation of NTT is based on this paper. This NTT is known as nega-cyclic convolution.
The rootOfUnityTable includes precomputed powers of a 2N-th root of unity modulo q, where N is the ring dimension.
The preconRootOfUnityTable tables are used for fast modular multiplication using Shoup’s modular multiplication by known constant and modulus.
So, regarding those two variables, if W is a 2N-th root of unity modulo q, the preconRootOfUnityTable includes precomputed powers of W’=floor(W*β/q), where β is the word-size (eg. 2^64), where W’ is the variable mentioned in Harvey’s Faster Arithmetic for Number Theoretic Transforms paper? Or is it something different?