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?

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