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?

Updated July 29, 2016 08:10 AM

Updated May 26, 2018 00:20 AM

- Serverfault Query
- Superuser Query
- Ubuntu Query
- Webapps Query
- Webmasters Query
- Programmers Query
- Dba Query
- Drupal Query
- Wordpress Query
- Magento Query
- Joomla Query
- Android Query
- Apple Query
- Game Query
- Gaming Query
- Blender Query
- Ux Query
- Cooking Query
- Photo Query
- Stats Query
- Math Query
- Diy Query
- Gis Query
- Tex Query
- Meta Query
- Electronics Query
- Stackoverflow Query
- Bitcoin Query
- Ethereum Query