1
$\begingroup$

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?

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

2 Answers 2

2
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

[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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.