Algorithm 1 INTT based on Gentleman-Sande butterfly [21]
Input: a = (a[0], a[1], ··· , a[N − 2], a[N − 1]), p,
Ψ−1 rev = (Ψ−1 rev[0], Ψ−1 rev[1], ··· , Ψ−1 rev[N − 1])
Output: a ← INTT(a)
1: t = 1
2: for (m = N; m > 1; m = m/2) do
3: j1 = 0
4: h = m/2
5: for (i = 0; i<h; i = i + 1) do
6: j2 = j1 + t − 1
7: W = Ψ−1 rev[h + i]
8: for (j = j1; j ≤ j2; j = j + 1) do
9: ButterflyUnit(a[j], a[j + t], W, p)
10: end for
11: j1 = j1 + 2 × t
12: end for
13: t = 2 × t
14: end for
15: return a
Procedure for the NTT
Suppose the input vector is a sequence of n non-negative integers.
Choose a minimum working modulus M such that 1≤n<M and every input value is in the range [0,M).
Select some integer k≥1 and define N=kn+1 as the working modulus. We require N≥M, and N to be a prime number. Dirichlet’s theorem guarantees that for any n and M, there exists some choice of k to make N be prime.
Because N is prime, the multiplicative group of ZN has size φ(N)=N−1=kn. Furthermore, the group must have at least one generator g, which is also a primitive (N−1)th root of unity.
Define ω≡gk mod N. We have ωn=gkn=gN−1=gφ(N)≡1 mod N due to Euler’s theorem. Furthermore because g is a generator, we know that ωi=gik≢1 for 1≤i<n, because ik<nk=N−1. Hence ω is a primitive nth root of unity, as required by the DFT of length n.
Thanks you