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

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

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?

Tags :

Related Questions

Updated December 05, 2017 18:20 PM

Updated April 04, 2019 23:20 PM

Updated July 29, 2016 08:10 AM

Updated July 24, 2018 21:20 PM

Updated May 26, 2018 00:20 AM