I recently heard that the Number Theoretic Transform (NTT), which is a specialization of Fast Fourier Transformation (FFT) over the ring modulo an integer, can be used to speed up certain calculations, if the operands are transformed before.
If I have matrices and vectors (with hundreds or few thousand entries) and want to do matrix-matrix or matrix-vector multiplication modulo an integer: would NTT be useful for speeding up this operations. And if yes, why/how?
If I have polynomials and want to do polynomial multiplication in a polynomial ring modulo another polynomial (for example $ x^n + 1$): would NTT be useful to speed up this calculations? And if yes, why/how?
I know that the possible advantage of NTT comes from the reduced complexity class. But I'm wondering if it is worth do to the transformation - calculatation - back transformation steps. Especially when I'm dealing with rather small numbers of the approximated size of 32 bit which fit into a machine register of an ordinary computer.