RNS 指 Residue Number System，是一種通用的用來表示數字和快速計算的一種方法。對於大數的模乘，模加等運算，使用 RNS 能夠轉化為多個較小數字的模乘模加，從而使得原本的運算能夠進行並行完成。
RNS 最初設計是用來並行化處理大數的運算。在抵禦旁路分析中，常常用掩碼技術（Masking）來將運算分解到多路上同時進行計算，使得攻擊者無法透過簡單功耗分析，探針等常規攻擊手段對秘密資訊進行窺探。而 RNS 系統似乎也能夠一定程度做到類似的事情（但洩露的資訊量仍有待研究）。
基本計算過程
轉換到 RNS 表示
將一個數字 $X$ 轉換到 RNS 表示是較為簡單的。首先選取定一組互質的數字作為 RNS 表示的基，之後對 X 按照基中的每個數字取模，得到的一組數字即是 $X$ 在該 RNS 下的表示。
$$ x_i = X \mod m_i $$
RNS 域上的計算
RNS 域上能夠進行模乘，模加和模減操作。除法在 RNS 表示下的計算無法使用相同的簡單方式，但也有一定的研究。 乘法，加法和減法的實現都是類似的，直接對錶示中數字分別進行模 $m_i$ 下的運算即可。
$$ z_i = x_i \odot y_i \mod m_i,~\textrm{where $\odot$ can be } +, -, \times. $$
這主要得益於中國剩餘定理。
從 RNS 表示中轉換出
從 RNS 表示中恢復原來的數字主要有兩種思路，一種是透過直接使用中國剩餘定理來進行恢復，另一種則使用了混合基數表示的方法，將 RNS 轉換到 MRS，再進行計算得到最終的結果。
中國剩餘定理（CRT）
\[ \begin{aligned} X = \sum_{i = 1}^k M_{i,1}\xi_i \mod M_1, \\ \xi_i = \left\vert\frac{x_i}{M_{i,1}}\right\vert_{m_i} = x_i \left\vert{M_{i,1}^{-1}}\right\vert \mod m_i, \\ M_{i,1} = \frac{M_1}{m_i}. \end{aligned} \]
然而，由於 $M_i$ 通常較大，$\mod M_i$ 仍然是較難計算的。因此在這種設計中，$\mod M_i$ 一般透過減去多倍的 $M_i$ 來實現。
\[ X = \sum_{i=1}^k M_{i,1}\xi_i \mod M_1 = \sum_{i=1}^k M_{i,1}\xi_i - \alpha M_1, \textrm{with} \alpha < k. \]
有兩種方法來計算其中的 $\alpha$.
- 由 Shenoy et. Kumaresan 提出的方法引入了一個額外的模數 $m_\text{extra}$, $\alpha$ 的估計值可以透過
\[ \begin{aligned} x_{\text{extra}} &= \left\vert {\sum_{i=1}^k {M_{i,1}} \xi_i - \alpha M_1} \right\vert_{m_\text{extra}} \Leftrightarrow \\ \left\vert {\alpha} \right\vert_{m_{\text{extra}}} &= \left\vert {\left\vert {\sum_{i=1}^{k}M_{i,1}\xi_i - x_{\text{extra}}}\right\vert_{m_\text{extra}}} {\left\vert {M_1^{-1}} \right\vert_{m_\text{extra}}} \right\vert_{m_\text{extra}} \end{aligned} \]
來進行計算。
- 由 Kawamura et. al 提出的方法避免了引入額外的模數，而使用了一種不動點逼近的方法。
混合基數表示（MRS）
混合基數表示中，各個權重分別為之前 RNS 基的連乘結果。
$$ X = \sum_{i=1}^{k} t_i \times (\prod_{j=1}^{i-1} m_j) $$
對於 MRS 中的各座標，計算如下：
\[ \begin{aligned} t_1 &= x_1 \\ t_2 &= \left\vert m_1^{-1} \right\vert_{m_2} \times (x_2 - t_1) \mod m_2 \\ t_3 &= \left\vert (m_1m_2)^{-1} \right\vert_{m_3} \times (x_3 - (t_2m_1 + t_1)) \mod m_3 \\ \vdots \\ t_i &= \left\vert (\prod_{j=1}^{i-1}m_j)^{-1} \right\vert_{m_i} \times (x_i - (\sum_{j=1}^{i-1}(t_j \prod_{l=1}^{j-1}m_l))) \mod m_i \\ \end{aligned} \]
MRS 表示中是精確的，不需要進行其他的分類討論和近似，因此在我們的最終的實現中，也使用的是轉化到 MRS 再進行計算。
RNS 基的選取
由於基需要是互質的整數，有以下幾種策略進行選取。
- 使用連續的質數
- 使用小質數的冪次，結合連續的質數
- 僅使用 $2^n$ 或者 $2^n - 1$ （Low-cost Moduli），便於模數運算
- 使用 $2^n +1$，$2^n$， $2^n - 1$，便於模數運算
除此之外，為了能夠表示所有的可用的座標，還需要保證 $\prod m_i $ 足夠大。
其他參考文獻：