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 $ 足够大。
其他参考文献：