多项式打包在$Z_{p^k}$和$F_{p^k}$上的局限性

### 多项式打包在 $Z_{p^k}$ 和 $F_{p^k}$ 上的局限性 #### 1. 引言 在处理满射打包方法时，零集相关的命题起着关键作用。我们在证明关于满射性的主要结果时会广泛使用这个命题。 #### 2. 零集理想命题 设 $R$ 和 $\hat{R}$ 为环。对于 $D > 1$，设 $(\text{Pack}_i, \text{Unpack}_i)_{i = 1}^D$ 是将 $R^n$ 映射到 $\hat{R}$ 的 $D$ 次满射打包方法。令 $Z_i$ 是由满足 $\text{Unpack}_i(a(x)) = 0$ 的元素 $a(x) \in \hat{R}$ 组成的集合。那么，存在 $\hat{R}$ 的某个理想 $Z$，使得 $Z = Z_1 = \cdots = Z_D$，并且 $|Z| = |\hat{R}|/|R|^n$。 证明如下： - 根据命题 13 和乘法同态性质，对于 $i < D$，有 $R \cdot Z_i \subset Z_{i + 1}$。 - 因为 $1 \in R$，所以 $Z_i \subset R \cdot Z_i$，进而 $Z_i \subset R \cdot Z_i \subset Z_{i + 1}$。 - 由命题 13 和加法同态性质可知，$Z_i$ 的大小相同，即 $|Z_i| = |\hat{R}|/|R|^n$。 - 因此，$Z_i = R \cdot Z_i = Z_{i + 1}$，可令 $Z := Z_1 = \cdots = Z_D$。又因为 $R \cdot Z = Z$，所以 $Z$ 是 $\hat{R}$ 的一个理想。 #### 3. $Z_{p^k}$ 消息打包的满射性 主要结果由以下定理给出，该定理阐述了 $Z_{p^k}$ 消息满射打包方法存在的必要条件。 - **定理 7**：设 $\check{r}$ 是 $f(x) \in Z_{p^t}[x]$ 在 $Z_{p^k}[x]$ 中模 $p$ 互异的线性因子的数量。对于 $D > 1$，存在将 $Z_{p^k}^n$ 映射到 $Z_{p^t}[x]/f(x)$ 的 $D$ 次满射打包方法的必要条件是 $n \leq \check{r}$。 - **证明概要**：设 $(\text{Pack}_i, \text{Unpack}_i)_{i = 1}^D$ 是将 $Z_{p^k}^n$ 映射到 $Z_{p^t}[x]/f(x)$ 的 $D$ 次满射打包方法。对于所有 $b(x) \in Z_{p^t}[x]/f(x)$，由满射性（命题 13）可知，存在 $b \in Z_{p^k}^n$ 使得 $\text{Unpack}_i(b(x)) = b$，所以 $\text{Unpack}_i(p^k \cdot b(x)) = 0$。这样，我们可以通过适当的投影和嵌入构造一个将 $Z_{p^k}^n$ 映射到 $Z_{p^k}[x]/f(x)$ 的 $D$ 次满射打包方法 $(\text{Pack}'_i, \text{Unpack}'_i)_{i = 1}^D$。然后，反复应用命题 14 可以证明，对于每个单位向量 $e_i \in Z_{p^k}^n$，存在 $a_i(x) \in Z_{p^k}[x]/f(x)$ 满足：(i) $\text{Unpack}'_1(a_i(x)) = e_i$；(ii) $a_i(x)$ 恰好在一个 CRT 槽位非零。最终，再次利用命题 14，可将每个 $a_i(x)$ 与 $f(x) \in Z_{p^k}[x]$ 的不同线性因子关联起来。 在继续之前，先给出关于 $\Phi_{2^m}(x)$ 在 2 的幂模下不可约性的一个简单事实。 - **命题 15**：对于 $M = 2^m$，分圆多项式 $\Phi_M(x)$ 模 4 不可约，即不存在 $f(x), g(x) \in Z_4[x]$ 使得 $f(x) \cdot g(x) = \Phi_M(x) \pmod{4}$ 且 $\text{deg}(f), \text{deg}(g) \geq 1$。 定理 7 有以下几个推论，它们说明了使用分圆多项式为 $Z_{2^k}$ 消息设计满射同态加密打包方法是不可能的。对于 $p \neq 2$ 的 $Z_{p^k}$ 消息也有类似结果。 | 示例编号 | 条件 | 结论 | | ---- | ---- | ---- | | 示例 23 | 当 $M = 2^m$ 时 | 无法在满足满射性和 2 次同态性的情况下，将 $Z_{2^k}$ 的任何副本打包到 $Z_{2^t}[x]/\Phi_M(x)$ 中 | | 示例 24 | 当 $M$ 为奇数时 | 无法在满足满射性和 2 次同态性的情况下，将 $Z_{2^k}$ 的任何副本打包到 $Z_{2^t}[x]/\Phi_M(x)$ 中 | | 示例 25 | 当 $M = 2^s \cdot M'$，其中 $M'$ 为奇数时 | 无法在满足满射性和 2 次同态性的情况下，将 $Z_{2^k}$ 的任何副本打包到 $Z_{2^t}[x]/\Phi_M(x)$ 中 | 定理 7 还表明，对于 $Z_{p^k}$ 消息，在伽罗瓦环上不存在有意义的满射 RMFE。 - **示例 26**：在 $GR(p^t, d) \cong Z_{p^t}[x]/f(x)$ 中，其中 $f(x)$ 是模 $p$ 不可约的 $d$ 次多项式，除非 $d = 1$，否则无法在满足满射性的情况下打包 $Z_{p^k}$ 的任何副本。 另一方面，有如下定理及其构造性证明，表明定理 7 中的必要条件也是充分条件。 - **定理 8**：假设 $f(x) \in Z_{p^t}[x]$ 在 $Z_{p^k}[x]$ 中有 $r$ 个模 $p$ 互异的线性因子，那么存在将 $Z_{p^k}^r$ 映射到 $Z_{p^t}[x]/f(x)$ 的满射打包方法。 - **证明**：设 $g(x) \in Z_{p^k}[x]$ 是 $f(x)$ 在 $Z_{p^k}[x]$ 中这些 $r$ 个线性因子的乘积。则存在一个 CRT 环同构 $\psi : Z_{p^k}^r \cong Z_{p^k}[x]/g(x)$。令 $\pi_k$ 和 $\iota_k$ 分别表示 $Z_{p^t}[x]/f(x)$ 和 $Z_{p^k}[x]/f(x)$ 之间的投影和嵌入，$\pi_g$ 和 $\iota_g$ 分别表示 $Z_{p^k}[x]/f(x)$ 和 $Z_{p^k}[x]/g(x)$ 之间的投影和嵌入。定义 $\text{Pack} := \iota_k \c