# The digit base and the NTT convolution

Suppose I'm using a number theoretic transform (NTT) in an integer field $GF(p)$. I assume that $2n$-th root of unity exists for such a $p$, and I want to compute a convolution of two $n$-length numbers with digit base $BASE$, thereby obtaining the product of the numbers.

However, these two things concern me the most:

1. What about overflows during the computation of $a = NTT(\bar{x_1})$, $b = NTT(\bar{x_2})$ and $c = INTT(a\times b)$? I am concerned with this because I'd rather use primitive-typed (e.g. long) arrays than arbitrary-precision numeric types.
2. Even if I use arbitrary precision arithmetic for each coefficient... How big can operands be in terms of $n$ and $BASE$ in order to obtain a correct cyclic convolution, with no information loss during modular reduction in the computation of $a, b$ and $c$, so that $c$, after carries, is a correct product? Is it enough that $BASE^2$ is less than $p$ (something in my memory tells me that the numbers in the convolution can be as large as $BASE^2$, it may be incorrect...). Or are there other nuances?

I suppose the worst-case scenario is when both numbers are $BASE^k - 1$ for some integer $k$, so clarifications for this scenario are most appreciated...

Thank you very much in advance!

-