Currently I am working on implementing a radix-4 NTT algorithm, but most of the research papers use a $2n$th root of unity as an input. However, in the Kyber specification, for $n = 256$ we don't have a $2n$th root mod $q=3329$, we only have an $n$th root which is 17. So how can one use the algorithm without the $2n$th root for $n = 256$?
$\begingroup$ $\endgroup$
1 
- $\begingroup$ It is called incomplet-NTT; You can check some resources on it $\endgroup$Don Freecs– Don Freecs2025-09-01 08:36:00 +00:00Commented Sep 1 at 8:36
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
2 We can use a 512th root of unity by working in the field $\mathbb F_{q^2}$, say for example using the representation as $\mathbb F_q[\omega]$ where $\omega^2=17$. Here all elements are of the form $a+b\omega$ where $a,b\in\mathbb F_q$ and for example $$(a+b\omega)(c+d\omega)=((ac+17bd)\mod q)+((ad+bc)\mod q)\omega.$$
- $\begingroup$ I dont understand,The radix 4 algorithm uses 2nth root of unity as its input but i only know its nth root,Also Why would u change the field? $\endgroup$Randomizer13_4– Randomizer13_42025-09-01 05:33:10 +00:00Commented Sep 1 at 5:33
- 2$\begingroup$ Because you do not have a $2n$th root of unity in $\mathbb F_q$ you must change to a field where you do. In this case $\mathbb F_{q^2}$ has a $2n$th root of unity which we write as $\omega$. $\endgroup$Daniel S– Daniel S2025-09-01 08:02:59 +00:00Commented Sep 1 at 8:02