As defined in Kyber's specification 1, the NTT consists of two formulas:
$$\hat{f}_{2i} = \sum_{j=0}^{127} f_{2j} \zeta^{(2 \cdot \text{br}_7(i)+1)\cdot j}$$
$$\hat{f}_{2i+1} = \sum_{j=0}^{127} f_{2j+1} \zeta^{(2 \cdot \text{br}_7(i)+1)\cdot j}$$
Judging by the formulas, I would assume that the NTT is now implemented in such a way that you have two vectors each of length 128 and then calculate two 128-point NTTs. But I have now noticed in the reference implementation 2 that the NTT uses a vector of length 256 as input.
/*************************************************
* Name: ntt
*
* Description: Inplace number-theoretic transform (NTT) in Rq.
* input is in standard order, output is in bitreversed order
*
* Arguments: - int16_t r[256]: pointer to input/output vector of elements of Zq
**************************************************/
void ntt(int16_t r[256]) {
unsigned int len, start, j, k;
int16_t t, zeta;
k = 1;
for(len = 128; len >= 2; len >>= 1) {
for(start = 0; start < 256; start = j + len) {
zeta = zetas[k++];
for(j = start; j < start + len; j++) {
t = fqmul(zeta, r[j + len]);
r[j + len] = r[j] - t;
r[j] = r[j] + t;
}
}
}
}
Apparently, this code looks to me as if the NTT is not split in the reference implementation but instead a full 256-point NTT is executed directly. But how can this work, when zeta is a 256th primitive root and we therefore also have to work with these two formulas. That's exactly why we have the two different formulas. However, in the implementation, it looks to me as if the following formula was used instead:
$$\hat{f}_{i} = \sum_{j=0}^{256} f_{j} \zeta^{(2 \cdot \text{br}_7(i)+1)\cdot j}$$
In short: For me, the implementation looks different than I would have expected it from the two formulas from above.
