RNS 到 MRS 的转换算法详解

1. 基本概念

1.1 剩余数系统（Residue Number System, RNS）

RNS 是一种非位权数制。给定一组两两互素的模数集合 {m₀, m₁, ..., m_{k-1}}，任意整数 X（在范围 [0, M) 内，其中 M = m₀ × m₁ × ... × m_{k-1}）可以用一组余数来唯一表示：

X = (x_{k-1} | x_{k-2} | ... | x₀)_{RNS(m_{k-1} | m_{k-2} | ... | m₀)}

其中 x_i = X mod m_i。

特点：RNS 各通道之间相互独立，加法和乘法可以并行完成，但比较大小和溢出检测非常困难。

1.2 混合基数系统（Mixed Radix System, MRS）

MRS 是一种位权数制。同一个整数 X 可以表示为：

X = (a_{k-1} | a_{k-2} | ... | a₀)_{MRS(m_{k-1} | m_{k-2} | ... | m₀)}

其展开式为：

X = a₀
  + a₁ × m₀
  + a₂ × m₀ × m₁
  + a₃ × m₀ × m₁ × m₂
  + ...
  + a_{k-1} × m₀ × m₁ × ... × m_{k-2}

其中每个系数满足 0 ≤ a_i < m_i。

特点：MRS 是位权表示，可以方便地进行大小比较，因此 RNS → MRS 的转换在实际应用中非常重要。

2. 转换算法

2.1 算法伪代码

Algorithm: Conversion from RNS to MRS

Input:  X = (x_{k-1} | x_{k-2} | ... | x₀)_{RNS(m_{k-1} | m_{k-2} | ... | m₀)}
Output: X = (a_{k-1} | a_{k-2} | ... | a₀)_{MRS(m_{k-1} | m_{k-2} | ... | m₀)}

1:  Y₀ := X
2:  a₀ = Y₀ mod m₀
3:  for i := 0 to k - 2 do
4:      Y_{i+1} = (Y_i - a_i) · |1/m_i|
5:      a_{i+1} = Y_{i+1} mod m_{i+1}
6:  end for

2.2 算法原理

算法的核心思想是逐步剥离 MRS 的各个系数，从最低位 a₀ 开始，依次求出 a₁, a₂, ..., a_{k-1}。

回顾 MRS 展开式：

X = a₀ + a₁·m₀ + a₂·m₀·m₁ + a₃·m₀·m₁·m₂ + ...

第 1 步：求 a₀

对 X 取模 m₀：

X mod m₀ = a₀    （因为后面所有项都包含因子 m₀，模 m₀ 后为 0）

第 2 步：消去 a₀ 并缩小问题

(X - a₀) = a₁·m₀ + a₂·m₀·m₁ + a₃·m₀·m₁·m₂ + ...

两边除以 m₀（在模运算中等价于乘以 m₀ 的模逆元 |1/m₀|）：

(X - a₀) / m₀ = a₁ + a₂·m₁ + a₃·m₁·m₂ + ...

此时新的值 Y₁ 的结构与原始问题完全相同，只是少了一位。对 Y₁ 取模 m₁ 即可得到 a₁。

第 3 步及之后：重复上述过程，直到所有系数都被提取出来。

2.3 关键操作：模逆元（Modular Multiplicative Inverse）

算法第 4 步中的 |1/m_i| 是 m_i 在其余各模数下的乘法逆元。

定义：a 在模 n 下的乘法逆元 a⁻¹ 满足 a · a⁻¹ ≡ 1 (mod n)。
逆元存在的充要条件是 gcd(a, n) = 1，即 a 与 n 互素。

由于 RNS 要求所有模数两两互素，因此 m_i 在其他所有模数 m_j（j ≠ i）下的逆元一定存在。

在 RNS 中，乘以 |1/m_i| 表示在每个剩余通道中分别乘以 m_i 对该模数的逆元。

3. 完整示例

3.1 问题

将 X = (7|4|1|1)_{RNS(9|7|5|2)} 转换为 MRS 表示。

模数集合为 {m₀, m₁, m₂, m₃} = {2, 5, 7, 9}（从右到左对应）。

3.2 预计算：所需的模逆元

逆元 计算方式 结果
2⁻¹ mod 5 2 × 3 = 6 ≡ 1 (mod 5) 3
2⁻¹ mod 7 2 × 4 = 8 ≡ 1 (mod 7) 4
2⁻¹ mod 9 2 × 5 = 10 ≡ 1 (mod 9) 5
5⁻¹ mod 7 5 × 3 = 15 ≡ 1 (mod 7) 3
5⁻¹ mod 9 5 × 2 = 10 ≡ 1 (mod 9) 2
7⁻¹ mod 9 7 × 4 = 28 ≡ 1 (mod 9) 4

说明：|1/m₀| = |1/2| 在各模数下分别为 (5|4|3|-)，其中 "-" 表示 m₀ 自身不参与。

3.3 逐步求解

初始状态：

Y₀ = X = (7|4|1|1)
               ↑
          对应模数: (9|7|5|2)

第 0 步：求 a₀

a₀ = Y₀ mod m₀ = 1 mod 2 = 1

在 RNS 中，Y₀ 的最右位 x₀ = 1 就是 X mod m₀ = X mod 2 的值。

第 1 步：求 Y₁ 和 a₁

1. 计算 Y₀ - a₀（在各通道分别减去 a₀ = 1）：

Y₀ - a₀ = (7|4|1|1) - (1|1|1|1)
         = (7-1 mod 9 | 4-1 mod 7 | 1-1 mod 5 | 1-1 mod 2)
         = (6|3|0|-)

最右通道（mod 2）已用完，标记为 "-"。

2. 乘以 |1/m₀| = |1/2|（各通道分别乘以 2 的逆元）：

Y₁ = (6|3|0|-) × (5|4|3|-)
   = (6×5 mod 9 | 3×4 mod 7 | 0×3 mod 5 | -)
   = (30 mod 9  | 12 mod 7  | 0 mod 5   | -)
   = (3|5|0|-)

3. 提取 a₁：

a₁ = Y₁ mod m₁ = 0 mod 5 = 0

取 Y₁ 对应 m₁ = 5 的通道值，即第二位（从右数）= 0。

第 2 步：求 Y₂ 和 a₂

1. 计算 Y₁ - a₁（各通道减去 a₁ = 0）：

Y₁ - a₁ = (3|5|0|-) - (0|0|0|-)
         = (3|5|-|-)

mod 5 的通道也已用完，标记为 "-"。

2. 乘以 |1/m₁| = |1/5|（各通道分别乘以 5 的逆元）：

Y₂ = (3|5|-|-) × (2|3|-|-)
   = (3×2 mod 9 | 5×3 mod 7 | - | -)
   = (6 mod 9   | 15 mod 7  | - | -)
   = (6|1|-|-)

3. 提取 a₂：

a₂ = Y₂ mod m₂ = 1 mod 7 = 1

第 3 步：求 Y₃ 和 a₃

1. 计算 Y₂ - a₂（各通道减去 a₂ = 1）：

Y₂ - a₂ = (6|1|-|-) - (1|1|-|-)
         = (5|-|-|-)

2. 乘以 |1/m₂| = |1/7|（仅剩 mod 9 通道）：

Y₃ = (5|-|-|-) × (4|-|-|-)
   = (5×4 mod 9 | - | - | -)
   = (20 mod 9  | - | - | -)
   = (2|-|-|-)

3. 提取 a₃：

a₃ = Y₃ mod m₃ = 2 mod 9 = 2

3.4 汇总结果

系数 值
a₀ 1
a₁ 0
a₂ 1
a₃ 2

最终转换结果：

X = (7|4|1|1)_{RNS(9|7|5|2)} = (2|1|0|1)_{MRS(9|7|5|2)}

3.5 验证

用 MRS 展开式还原十进制值：

X = a₀ + a₁·m₀ + a₂·m₀·m₁ + a₃·m₀·m₁·m₂
  = 1 + 0×2 + 1×(2×5) + 2×(2×5×7)
  = 1 + 0 + 10 + 140
  = 151

用 RNS 验证：

151 mod 2 = 1  ✓
151 mod 5 = 1  ✓
151 mod 7 = 4  ✓
151 mod 9 = 7  ✓

两种表示一致，转换正确。

4. 算法复杂度与特点

方面 说明
时间复杂度 O(k²)，共 k-1 次迭代，每次迭代对剩余通道做减法和乘法
所需预计算 所有 m_i 在 m_j (j > i) 下的模逆元，共 k(k-1)/2 个
优势 转换后可直接比较大小、检测溢出
局限 过程是串行的——必须先求出 a_i 才能求 a_{i+1}

5. 总结

RNS → MRS 转换的本质是一个逐步剥离的过程：

  1. 对最小模数取模，得到最低位系数
  2. 减去该系数，使结果能被当前模数整除
  3. 在模运算下"除以"当前模数（乘以模逆元）
  4. 丢弃已用完的通道，对下一个模数重复上述过程

这一过程将 RNS 的非位权表示转化为 MRS 的位权表示，从而解决了 RNS 中难以直接完成的大小比较等问题。