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

-

## 1 Answer

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 18, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9048110842704773, "perplexity_flag": "middle"}