pq-crystals/kyber

Why NTT and INTT use the same zeta array only with different order? and Why signed number is used not unsigned number?

lizhirui opened this issue · 1 comments

I notice that NTT and INTT use the same(not different) zeta array(ref/ntt.c) since commit.

Why is it effective?

And, in Dilithium implementation, intt also uses the same zeta array with ntt except zeta = -zetas[k--] not zeta = zetas[k--], that's why?

In Kyber and Dilithium implementation, why signed number is used not unsigned number?

The values in the zeta array are the same for forward and inverse NTT,
they are just used in a different order. So, using the same array saves
some space and keeps the code simpler.

Using signed representation can have a small advantage for lazy-reduction
strategies, but if you prefer, you can also use unsigned representation.
If you do, you will have to update the modular reduction algorithms then and
carefully check where reductions are needed to avoid overflows.