A-13.1 Application: Residue Number System (RNS)

In a modern processor, each data size is a maximum of 64 bits. If the data size exceeds 64 bits, its computations can be handled efficiently by using the Chinese remainder theorem such that each co-prime modulus ${\log <!--\; FUNCTION\; APPLICATION\; -->}_2{n}_i\le 64$ (where $N=n_0\cdot n_1\cdots \cdot n_k$) can be used to represent a big value $amodN$ as ${\overrightarrow{a}}_{\mathrm{𝑐𝑟𝑡}}=(a_0,a_1,\cdots ,a_k)$, where $a\equiv a_{i}mod{n}_i$. Then, for any pair of big numbers $a$ and $bmodN$, we can compute $a+bmodN$ and $a\cdot bmodN$ as follows:

• $a+b\equiv \underset{i=0}{\overset{k}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_i{y}_i{z}_i+\sum _{i=0}^k{b}_i{y}_i{z}_i\equiv \sum _{i=0}^k{a}_i{y}_i{z}_i+b_i{y}_i{z}_i\equiv \sum _{i=0}^k(a_i+b_i)y_i{z}_{i}modN$

  $$

• $a\cdot b\equiv \underset{i=0}{\overset{k}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_i{y}_i{z}_i\cdot \sum _{i=0}^k{b}_i{y}_i{z}_i\equiv \sum _{i=0}^k(a_i\cdot b_i){(y_i{z}_i)}^2+\sum _{i\ne j}^k(a_i\cdot b_j)y_i{z}_i{y}_j{z}_j\equiv \sum _{i=0}^k(a_i\cdot b_i){(y_i{z}_i)}^2$

  # Note that all terms $y_i{z}_i{y}_j{z}_j$ where $i\ne j$ are 0 modulo $N$, because $y_i{y}_{j}modN\equiv 0$.
  This is because $y_i=n_0{n}_1\cdots n_{i-1}{n}_{i+1}\cdots$ and $y_j=n_0{n}_1\cdots n_{j-1}{n}_{j+1}\cdots$.
  Thus $y_i{y}_j$ is a multiple of $N$.

  $$

  $\equiv \underset{i=0}{\overset{k}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(a_i\cdot b_i)(y_i{z}_i)modN$

  # This is because $(y_i{z}_i)\equiv {(y_i{z}_i)}^2$ as shown in step 3 in the proof of Theorem A-13.1

Thus, the Chinese remainder theorem gives us the following useful formula: