我们开启一个新的系列，来读一读代码和相关技术文档。这里从微软的同态加密库SEAL开始。

CRT Batching 允许用户将模 t 下的 n 个整数打包成一个明文多项式，并以SIMD（单指令，多数据）方式对这些整数进行操作。在同态加密文献中，这种技术通常称为批处理。有关更多详细信息和应用，参阅文献[1,2]。

批处理（batching）仅在明文模数t被选为素数并且与 1(\bmod 2n) 同余的情况下起作用，我们假设这是成立的。在这种情况下，整数模 t 的乘法群包含一个大小为 2n 的子群，这意味着存在一个整数 ζ∈\mathbb Z_t ，使得对于所有 0 < m < 2n，有ζ^{ 2n} = 1 (\bmod t) 且ζ^{m} \ne 1 (\bmod t)。这样的元素 ζ 称为模 t 的一个 2n 次本原根。拥有模 t 下的 2n 次本原根很重要，因为此时多项式模 x^n + 1 能够分解为 (x − ζ)(x − ζ ^3 )…(x − ζ^{ 2n−1} ) (\bmod t) ，并且根据中国剩余定理（CRT），环 R_t 也能分解为

R_{t}=\frac{\mathbb{Z}_{t}[x]}{\left(x^{n}+1\right)}=\frac{\mathbb{Z}_{t}[x]}{\prod_{i=0}^{n-1}\left(x-\zeta^{2 i+1}\right)} \stackrel{\mathrm{CRT}}{\cong} \prod_{i=0}^{n-1} \frac{\mathbb{Z}_{t}[x]}{\left(x-\zeta^{2 i+1}\right)} \cong \prod_{i=0}^{n-1} \mathbb{Z}_{t}\left[\zeta^{2 i+1}\right] \cong \prod_{i=0}^{n-1} \mathbb{Z}_{t} \\

这里的 R_t 是在模 t 意义下的整数环 \mathbb{Z}_t[x] 模 x^n+1 的商环，即 R_t = \mathbb{Z}_t[x]/(x^n+1)。假设 t 是一个满足 t \equiv 1 \pmod{2n} 的质数，则在模 t 意义下，存在一个大小为 2n 的整数子群，意味着存在一个元素 \zeta \in \mathbb{Z}_t 满足 \zeta^{2n} = 1 \pmod{t}，且 \zeta^m \neq 1 \pmod{t} 对于所有 0 < m < 2n 均成立。这个元素 \zeta 被称为模 t 意义下的 2n 次本原单位根。

由于 t 是质数，因此在模 t 意义下 \mathbb{Z}_t 是一个域，也就是说 \mathbb{Z}_t[x] 是一个唯一分解整环。因此，根据唯一分解定理，我们可以将 x^n+1 分解成 n 个一次多项式的积，即

x^n+1 = \prod_{i=0}^{n-1} (x - \zeta^{2i+1}) \pmod{t}\\根据中国剩余定理，我们可以将 R_t 表示为 n 个 \mathbb{Z}_t[x] 模 (x-\zeta^{2i+1}) 的乘积：

R_t \stackrel{\mathrm{CRT}}{\cong} \prod_{i=0}^{n-1} \frac{\mathbb{Z}_t[x]}{(x-\zeta^{2i+1})} \\

每个 \frac{\mathbb{Z}_t[x]}{(x-\zeta^{2i+1})} 都是一个整环，也就是一个域的扩张，可以看作是 \mathbb{Z}_t 上的扩域，因此它们是同构的，即

\frac{\mathbb{Z}_t[x]}{(x-\zeta^{2i+1})} \cong \mathbb{Z}_t[\zeta^{2i+1}]\\

因此，R_t 同构于 \prod_{i=0}^{n-1} \mathbb{Z}_t[\zeta^{2i+1}]，也就是 n 个 \mathbb{Z}_t 上的扩域的直积。这个结论说明了，我们可以将 R_t 中的多项式视为 n 个 \mathbb{Z}_t 中的数的向量，其中向量的每个分量都是模 t 意义下的一个 \mathbb{Z}_t 上的扩域元素。在这个向量空间上进行运算，就实现了 SIMD 加速。

以上的同构映射都是环同构，这意味着它们在两边都保持乘法和加法结构，可以用一个 R_t 中的一次加法（或乘法）来实现模 t 下 n 个整数的逐项加法（或乘法）。这些同构映射可以明确地描述出来。为了简单起见，令 α_i = ζ^{ 2i+1} 。其中一个方向的同构映射由以下公式给出：\text { Decompose }: R_{t} \stackrel{n-1}{\longrightarrow} \prod_{i=0}^{n-1} \mathbb{Z}_{t}, m(x) \longmapsto\left[m\left(\alpha_{0}\right), m\left(\alpha_{1}\right), \ldots, m\left(\alpha_{n-1}\right)\right]\\定义Compose为Decompose的逆。这些同构是使用数论变换（NTT）的 negacylic 变体计算得出的。

在SEAL中，Compose和Decompose转换为和从明文多项式转换的 n 维 \mathbb Z_t 向量可以看作是一个 2×(n/2) 矩阵。

当正确使用时，批处理可以大大提高性能。当在加密整数而不是在 t 模数下的整数上使用批处理进行计算时，需要确保插槽中的值在计算期间不会 wrap around t。可以通过选择足够大的 t 来解决，但这将不幸地导致噪声增长。

[1] Zvika Brakerski, Craig Gentry, and Shai Halevi. Packed ciphertexts in LWE-based homomorphic encryption. In Public-Key Cryptography–PKC 2013, pages 1–13. Springer, 2013.

[2] Nigel P Smart and Frederik Vercauteren. Fully homomorphic SIMD operations. Designs, codes and cryptography, 71(1):57–81, 2014.