Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.