# Question on Number Theoretic Transformation (NTT) Condition

For the NTT I know the following preconditions, which must be fulfilled for the primitive $$N$$-th root of unity:

$$\omega^N \equiv 1$$ $$\sum_{i=0}^{N-1} \omega^{ik} \equiv 0 \quad k=1,\ldots,N-1$$

These are derived from the DFT and adapted to the modular arithmetic of the NNT. So far clear.

But what about this condition:

$$\underbrace{1+1+\cdots+1}_{N} \not\equiv 0$$

What if

$$\underbrace{1+1+\cdots +1}_{N} \equiv 0$$

would apply? What consequence would this have?

• I think your questions are not clear can you elaborate more? Commented Aug 25, 2023 at 20:03
• Are you considering that $\omega^{ik}$ are all one in the sum? If so, that is not true! Commented Aug 25, 2023 at 20:37

## 2 Answers

In slightly more detail, the condition for fast NTT multiplication in the ring

$$\mathbb{Z}_q[x] / (x^{n}+1)$$

where $$n = 2^k$$ is that $$q\equiv 1\bmod 2n$$. Your other question seems to be "what happens when $$n\equiv 0\bmod q$$?". This will essentially never happen, because in essentially all applications $$q = \mathsf{poly}(n)$$ (for both correctness and security), so $$n\bmod q = n$$ (without modular reduction), which cannot be zero for security reasons (it must be $$\geq 512$$ at a minimum for RLWE. It can be lower for MLWE, but the smallest it can be is 1, e.g. standard LWE, but here we don't do NTT type things anyway).

[You question is addressed at the end; first some math.]

The parameter $$n$$ is usually taken to be a power of two because

• $$x^n+1$$ is irreducible over $$\mathbb{Q}$$ for powers of 2 (nice for theoretical lattice problems),
• the FFT is nicest for powers of 2.

For $$x^n+1$$ to split completely over the base field $$\mathbb{F}_q$$, i.e. to get the nice ring homomorphism $$\mathbb{F}_q[x]/(x^n+1)\cong \prod_{i=0}^{n-1}\mathbb{F}_q[x]/(x-\zeta^{2i+1})\cong \mathbb{F}_q^n,$$ we need a primitive $$2n$$th root of unity $$\zeta\in\mathbb{F}_q$$. The multiplicative group $$\mathbb{F}_q^{\times}$$ has order $$q-1$$, so we need $$2n|q-1$$ or $$q\equiv 1\bmod 2n$$.

In this case the ring isomorphism above is given by evaluation-interpolation/DFT/Chinese remainder theorem (whatever you want to call it), $$f(x)\mapsto (\ldots, f(\zeta^{2i+1}),\ldots)$$ or as a linear transformation is given by matrix multiplication (on the coefficients of the polynomial $$f$$ of degree $$<$$ n) $$\mathcal{F}=\left(\zeta^{(2i+1)j}\right)_{i,j\geq 0}$$ with inverse $$\mathcal{F}^{-1}=\frac{1}{n}\left(\zeta^{-(2j+1)i}\right)_{i,j\geq 0}.$$ These linear transformations can be done quickly using the FFT (nice to have $$n$$ a power of two to break this down nicely, Cooley--Tukey/DIT or Gentleman--Sande/DIF).

The point is to replace polynomial/"negacyclic" multiplication (naive $$n^2$$ coefficient multiplications) with pointwise multiplication ($$n$$ coefficient multiplications) at the cost of doing the NTT ($$n\log n$$-ish).

This is slightly different from the usual DFT/FFT using all roots of unity $$x^n-1$$, but not by much.

Also, note that you don't need things to split into linear factors to get savings (e.g. $$q=3329$$, $$n=256$$ in Kyber).

Addressing your question, with the above (say $$q$$ prime and $$n$$ a power of 2), $$q$$ doesn't divide $$n$$ so $$n\neq0$$. Moreover, you wouldn't want this as the linear transformation $$\mathcal{F}$$ wouldn't be invertible and $$x^n+1$$ would ramify, e.g. $$x^q+1=(x+1)^q$$.