0
$\begingroup$

I've been reading about NTT (Number Theoretic Transform) for multiplication of two polynomials. I followed this tutorial for the same Number-theoretic transform (integer DFT).

In this post, after representing two polynomials in vector form and converting them into NTT domain, they perform point-wise multiplication of both the transforms, after the multiplication they perform inverse NTT transform of resultant vectors to get some form of circular convolution.

Z=INTT(Z′)=(123,120,106,92,139,144,140,124).

Screenshot of the respective step of the Post referred from above

So, my question is How to represent this resultant product transform back into polynomial form, such that the resulting polynomial is the same as the one we would've got if we had performed normal multiplication of the polynomials in time domain without NTT.

Please help, Thank you

$\endgroup$

1 Answer 1

1
$\begingroup$

$NTT$ and $DFT$ are effectively the same, and there are a lot of sources where you can understand $DFT$, in case you're confused on how $NTT$ works.

Basically with $NTT$ we can compute convolutions of the form $c_k = \sum_{i=0}^{n-1}a_i b_{k-i}$ modulo $N$ (prime), where the indices are modulo $n$ (e.g $b_{-1} = b_{n-1}$), the site gives this formula as $Z(i) = \sum_{j=0}^{n-1}X(i)Y((j-i) \mod n)\pmod N$.

Now, how can we multiply $A(x) = \sum_{i=0}^{n_a-1}a_ix^i$ and $B(x) = \sum_{i=0}^{n_b-1} b_ix^i$ ?

We just need to compute the coefficients $c_k = \sum_{i=0}^k a_i b_{k-i}$, so that $$C(x) = (A\cdot B)(x) = \sum_{i=0}^{n_a+n_b-1}c_ix^i$$

Given than we can only compute the "circular convolution" (the first formula i've mentioned) we need to do something different to compute the coefficients $c_k$. What if, instead of each polynomial being degree $n_a-1, n_b-1$ we though both of them as polynomials of degree $n = n_a + n_b - 1$ with padded zeroes? (I use $n_x$ for the length of a sequence $X$ while the corresponding polynomial is of degree $n_x-1$)

Now padding $A(x)$ and $B(x)$ with zeroes, during the circular convolution of $(a_m)$ with $(b_m)$ at small values of $k$ which move out of bounds in $a_i$, $b_{k-i}$ the product $a_i b_{k-i}$will be $0$, and so it won't be counted in $c_k$.

There are a lot of implementations of $DFT$ for polynomial multiplcation you can lookup (since $NTT$ implementations may be more scarce).

$\endgroup$

You must log in to answer this question.

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