经典与量子算法及多元二次多项式问题求解

# 经典与量子算法及多元二次多项式问题求解 ## 1. 通用综合征的经典与量子算法 ### 1.1 函数 \(f\) 的构造与计算 对于固定的 \(k\)，若存在 \(y_1', \cdots, y_{2a - 1}'\)，使得每个 \(y_i' \in L_i\) 且 \(\sum_{i} y_i' + y_{2a}^k = s\)（即属于 \(L_{top}\)），我们可以得到与 \(i \in [2a - 1]\) 相关的 \(b_i\)，满足 \(H b_i = y_i'\)，且 \(H b_{2a} = y_{2a}^k\)。此时令 \(e_k = \sum_{i} b_i\)，若存在多个这样的向量，则按照字典序取第一个。若该等式成立，则 \(H e_k = s\)。我们定义函数 \(f\) 如下： \[ f(k) = \begin{cases} e_k \text{（上述定义）}, & \text{若这样的向量存在}\\ 0, & \text{否则} \end{cases} \] 构造 \(f\) 的步骤如下： 1. 为除最右侧列表外的每个楼层构造所有列表。 2. 根据相应 \(J_j\) 的索引，按字典序对这些列表进行排序。 3. 对于输入 \(k\)，从 \(y_{2a}^k\) 开始，尝试将其与左侧相邻列表中的元素 \(y'\) 相加，使和出现在顶部列表中（若有多个，按字典序取第一个）。这可以通过二分搜索在列表大小的对数时间内高效完成。 4. 重复上述过程，直到失败（输出 0）或到达顶部列表，然后输出相应的 \(e_k\)。 构造和排序列表以计算 \(f\) 需要时间 \(qN(u' + o(1))\)（省略常数乘法项 \(2a\)），但后续计算 \(f\) 只需多项式时间。使得 \(f(k)\) 输出有效解的 \(k\) 的数量实际上就是 \(L_{top}\) 的大小，即 \(qN(3u' - x)\)，由于 \(f : [Y] \to F_q^n\)，这证明了相关命题。 ### 1.2 计算表面积 考虑一个大小为 \(n\) 的多重集，其元素取自 \(\{0, \cdots, q - 1\}\)，每个元素重复 \(c_i\) 次，\(i \in \{0, 1, \cdots, q - 1\}\)。这样的多重集的排列数由多项式系数定义： \[ \begin{pmatrix} n \\ c_0, c_1, \cdots, c_{q - 1} \end{pmatrix} \stackrel{\text{def}}{=} \frac{n!}{c_0! c_1! \cdots c_{q - 1}!} \] 这个数对应于由 \(c_0\) 个零、\(c_1\) 个一、\(\cdots\)、\(c_q\) 个 \(q\) 组成的向量的数量。 进一步定义 \(C = \{c = (c_0, \cdots, c_{q - 1}) : i \in \{0, 1, \cdots, q - 1\}, c_i \in \mathbb{N}, \sum_{i = 0}^{q - 1} c_i = n, \sum_{i = 0}^{q - 1} c_i \text{wt}'(i) = w\}\)。根据球面表面积的定义，我们有： \[ S_n^w = \sum_{c \in C} \begin{pmatrix} n \\ c \end{pmatrix} \] 对于固定的 \(n\) 和 \(q\)，集合 \(C\) 的大小（即求和项的数量）上界为 \(\begin{pmatrix} n + q - 1 \\ q - 1 \end{pmatrix}\)。因此，\(S_n^w\) 的上下界为： \[ \max_{c \in C} \begin{pmatrix} n \\ c \end{pmatrix} \leq S_n^w \leq \begin{pmatrix} n + q - 1 \\ q - 1 \end{pmatrix} \max_{c \in C} \begin{pmatrix} n \\ c \end{pmatrix} \] 按照特定推理方式，即对上述方程的每一部分取以 \(q\) 为底的对数，乘以 \(\frac{1}{n}\)（其中 \(n \to +\infty\)），并使用斯特林近似，最终可得到方程 (5)。 ### 1.3 凸优化问题 问题 3 属于凸优化问题的子类，即锥优化问题。因此可以使用 MOSEK 求解器来解决。不过，为了能通过 MOSEK 求解，问题 3 需要转换为锥优化问题的标准形式，即问题 4： 设 \(\lambda = (\lambda_0, \lambda_1, \cdots, \lambda_{q - 1}) \in \mathbb{R}_+^q\) 且 \(\tau = (\tau_0, \tau_1, \cdots, \tau_{q - 1}) \in \mathbb{R}_+^q\)。 - 最大化：\(\sum_{i = 0}^{q - 1} \tau_i\) - 约束条件： - \(\sum_{i = 0}^{q - 1} \lambda_i = 1\) - \(\sum_{i = 0}^{q - 1} \lambda_i \text{wt}'(i) = \omega\) - \((1, \lambda, \tau) \in K_{exp}\)，其中约束 \((1, \lambda, \tau) \in K_{exp}\) 表示对于每个 \(i \in \{0, 1, \cdots, q - 1\}\)，\(\tau_i \leq - \lambda_i \log_q \lambda_i\)。 可以很容易验证问题 3 和问题 4 是等价的，因此求解其中任何一个都能得到球面表面积的渐近值。 ## 2. 多元二次多项式问题求解 ### 2.1 多元二次多项式问题概述 多元二次多项式问题（MQ 问题）是后量子密码学中的一个基本计算问题。我们用 \(MQ(q, n, m)\) 表示在有限域 \(F_q\) 上 \(n\) 个变量的 \(m\) 个二次方程的 MQ 问题。若 \(n > m\)，则系统为欠定的；若 \(n < m\)，则为超定的。该问题是 NP 完全的，因此被认为有潜力抵抗量子计算机的攻击。 ### 2.2 混合方法 给定在 \(F_q\) 上 \(n\) 个变量的二次多项式系统 \(P = (p_1, \cdots, p_m)\)，考虑系统 \(P(x) = 0\)。假设变量数量 \(n\) 小于或等于方程数量 \(m\)（若 \(n > m\)，可以随机指定 \(n - m\) 个变量，大概率不影响解的存在性）。 二次系统可以使用 XL 算法或 Gröbner 基技术（如 F4 和 F5 算法）求解。此外，我们引入混合方法，它将穷举搜索与 MQ 求解器（如 XL、F4 或 F5）相结合。在这种方法中，对于 \(0 \leq k \leq n - 1\)，在将 MQ 求解器应用于剩余 \(n - k\) 个变量的系统之前，随机猜测 \(k\) 个变量，重复此过程直到找到解。使用 Wiedemann XL 的复杂度，混合方法的复杂度估计为： \[ O \left( q^k \cdot 3 \cdot \binom{n -