8
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

FTT transforms for multiplications are only useful for very big numbers. The complexity hides a big constant factor. If you have to write algorithms for cryptography involving huge numbers, use it. But for small integers, you will waste time

$\endgroup$
1
$\begingroup$

NTT can be useful for polynomial multiplication in a polynomial ring. If you transform coefficients to the NTT domain, the multiplication between coefficients of two polynomials is component-wise.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.