# In dilithium (post quantum signature algorithm), how have the authors precomputed the table of zetas for NTT?

I am trying to understand the design rationale of in place NTT in Dilithium. I know that how the splitting of polynomials is done but I cant seem to map this approach to the precomputed table of zetas that is present in the authors code. I have attached the array of values as well. Specifically speaking, is there a way to calculated these values by ourselves? If yes, then how can this be done? Any help regarding this would be very very helpful.

• please give a link to a definition of zeta or explain it. same for NTT. it is a good idea to make your questions detailed and complete. Aug 24, 2023 at 12:13

I did not try to implement the algorithm myself but those values are powers of $$\zeta = 1753 \in \mathbb{Z}_q$$ (as hinted by the name) in the Montgomery form where $$q = 8380417$$ and the elements of $$\mathbb{Z}_q$$ are represented not as $$\{0,\dots, 8380416\}$$ but as $$\{-\frac{8380416}{2},\dots,0,\dots, \frac{8380416}{2}\}$$. Montgomery form is calculated by multiplying by $$2^{32}$$ and reducing $$\mod q$$.

Source: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.ipd.pdf (Section 8.5 mainly)

In more detail, each value is $$\zeta_k = \zeta^{\text{brv}(k)}\mod q$$. Where $$\text{brv}()$$ is the bit reversal operation (see the specification for definition), e.g., $$\text{brv}(1)=128,\text{brv}(2)=64$$. This corresponds with the values listed.

$$\zeta_1 = \zeta^{\text{brv}(1)}=\zeta^{128} \mod q = 4808194$$

Now we convert to Montgomery representation and the $$\mathbb{Z}_q$$ representation.

$$4808194\cdot 2^{32} \mod q = 25847$$. We get the second value. Similarly,

$$\zeta_2 = \zeta^{\text{brv}(2)}=\zeta^{64} \mod q = 3765607$$

$$3765607\cdot 2^{32} \mod q = 5771523$$. This is bigger than $$\frac{8380416}{2}$$ so we need to reduce.

We need to find a number $$\alpha$$ in $$\{-\frac{8380416}{2},\dots,0,\dots, \frac{8380416}{2}\}$$ s.t. $$\alpha = 5771523 \mod q$$ which is $$5771523-q=-2608894$$ which is the third value in the array.

The first value in the array ($$0$$) seems to be just a placeholder to properly index the array (since you want to access elements at indices $$1-255$$ and not $$0-254$$. Since in the code they do pre-increment https://github.com/pq-crystals/dilithium/blob/master/ref/ntt.c#L56.

• Thank you Sir. This is the exact solution that I was looking for. Aug 25, 2023 at 9:38