2
$\begingroup$

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!

1 Answers 1

1

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