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$

2 Answers 2

2
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .