Is it possible to perform subtraction on NTT form of two integers?

by Robert   Last Updated June 12, 2019 07:20 AM - source

Using number theoretic transform (NTT) is a means of performing efficient multiplication of large integers. The NTT notation of an integer is a vector. One can perform element-wise multiplication of two NTT vectors to compute an integer multiplication. As I've tested it is also possible to perform element-wise addition on vectors to compute integer addition. However, element-wise subtraction does not yield the correct result if any element become negative.

To be more precise, suppose $A$ and $B$ are two integers and $a = NTT(A)$ and $b=NTT(B)$. We know that $$A+B=INTT(a+b)$$ and $$A\times B=INTT(a \times b).$$ However, if any element gets negative in $a-b$, $$A-B\neq INTT(a-b).$$

Is there any work around to solve the issue regarding subtraction?



Related Questions





If $x^3$ is a square, is $x$ a square?

Updated June 19, 2019 16:20 PM