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: 


*

*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.

*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!

I found a good explanation in 
Overflow Detection in the Computation of Convolutions
by Some Number TheoreticTransforms
HENRI J. NUSSBAUMER
0096-35 18/78/0200-0109$00.75 0 1978 IEEE
IEEE TRANSACTIONS  ON ACOUSTICS, SPEECH, SIGNAL AND PROCESSING, 108 VOL. ASSP-26, NO. 1 , FEBRUARY 1978
I cannot send to you the papaer because of copyright
