Automated Coppersmith 的渐近界：线性规划对偶与一个精确 SageMath 实现

Reading: Ding et al., ePrint 2026/1027。本文只处理一个问题：Automated Coppersmith 的 shift 选择为什么在缩放后变成线性规划，以及 Theorem 4 中的渐近系数如何写成 \(P\) 上的积分。¹

主链为：shift 可行性 → 逐点 ILP → 缩放 LP → 对偶分片 → Ehrhart 积分。实现部分检查 auto-copper 如何用精确有理数计算对偶顶点、满维单元格与积分，并用有限参数例子核对 Algorithm 2。

问题设定与 notation

论文是 Zhaopeng Ding、Zhaopeng Dai、Baofeng Wu、Yanshuo Zhang、Kejun Zhang 的 Computing Asymptotic Bounds for the Automated Coppersmith Method via Linear Programming。¹ auto-copper 是对应的 SageMath 10.6 实现。下文的数学链取自论文，实现细节取自仓库源码，实验数字来自本机运行。

考虑同余系统

其中每个 \(f_j\in\mathbb{Z}[x_1,\dots,x_k]\) 是非零、非平凡、首一（monic）的多项式，且常数单项式在支撑里，即 \(0\in A(f_j)\)。\(A(f_j)\) 表示非零系数对应的指数集。设

为按固定单项式序取的首项单项式，\(\mathbf{e}=(e_1,\dots,e_n)\in\mathbb{Z}_{>0}^n\) 是模数指数向量。目标是恢复共同小根 \(x^{(0)}\)，满足 \(|x_i^{(0)}|\lt X_i\)，其中 \(X_i\) 是预先给定的正界。

Automated Coppersmith 的输入里还有一个有限单项式集 \(M_m\)。在渐近层，论文取

其中 \(P\subseteq\mathbb{R}_{\ge 0}^k\) 是满维有理多胞体。问题是：当 \(m\to\infty\) 时，哪些 \(X_i\) 的组合可以被该构造恢复，即求形如

的渐近界。

边界：从 equation (3) 起步

仓库从论文的 equation (3) 起步：调用方先把密码系统中的原始方程预处理成 \(f_j(x)\equiv 0 \pmod{M^{e_j}}\) 的形式。CIHNP 或 MIHNP 背后的 Gröbner 消元不在实现范围内。后文使用三个边界条件：cancellation-free、Assumption 1，以及从 equation (3) 开始。

这里有一个容易被标题遮住的分层。论文所说的 automated，不是把“一个密码问题”自动变成“一个可运行的 Coppersmith attack”。它接管的是中间一段：在同余系统、项序和单项式区域已经确定以后，怎样选择 shift，以及怎样计算这组选择在 \(m\to\infty\) 时给出的行列式指数。原始协议如何消元、哪些变量应当当作小量、应该选哪种项序、根恢复是否成功，都在这段自动化之外。

我更愿意把输入看成一份已经完成代数建模的 IR（intermediate representation）。Equation (3) 类似一个编译器中间层：上游把 CIHNP、MIHNP 或 ECHNP 的协议关系降到若干带模幂的多项式；论文处理这个 IR 上的 shift optimization；下游再把辅助多项式交给 Gröbner basis、resultant 或 variety 求根。这样理解后，论文的贡献边界会清楚很多。它自动化了中段，而且把中段原来依赖插值猜测的部分换成了可证明公式；它没有解决上游建模和下游求根两个同样困难的问题。

Reading Note. 后面每次看到“可恢复”都要区分两层含义。Theorem 4 给出的是满足行列式渐近条件的参数区域；实际恢复还要经过有限维格规约、Howgrave–Graham 筛选和 Assumption 1。把这两层合并，会把一个 asymptotic bound 误读成端到端攻击保证。

从原论文到通用骨架

一元情形完整推导

设 \(f(x)\in\mathbb{Z}[x]\) monic、\(\deg f=\delta\)，目标是在模 \(N\) 下找小根 \(x_0\)，\(|x_0|\lt X\)。原论文（以及 Howgrave–Graham 的重述）用的 shift 族是

每个 \(g_{i,j}\) 在 \(x_0\) 处模 \(N^t\) 为零：\(f(x_0)^j\) 贡献 \(N^j\)，\(N^{t-j}\) 补到 \(N^t\)。单项式集是 \(\{1,x,\dots,x^{\delta t-1}\}\)，一共 \(n=\delta t\) 个；基矩阵按升序排是三角的，因为 \(g_{i,j}\) 的首项 \(x^{i+\delta j}\) 恰好覆盖全部指数各一次。

行列式可以直接算。\(N\) 的指数是 \(\sum_{j=0}^{t-1}(t-j)\delta=\delta t(t+1)/2\)；\(X\) 的指数是

所以

LLL 给第一短向量 \(\|b_1\|\le2^{(n-1)/4}\det^{1/n}\)；Howgrave–Graham 要求 \(\|b_1\|\lt N^t/\sqrt{n}\)。合并后两边取 \(n\) 次方、常数因子收进 \(N^{-\varepsilon}\)：

所以渐近地说 \(X\lt N^{1/\delta-\varepsilon}\) 可恢复。若只知道 \(f(x)\equiv0\pmod b\)、\(b\mid N\)、\(b\ge N^\beta\)，经典结果把界换成 \(X\lt N^{\beta^2/\delta}\)；完整证明见 ²，这里不展开。

这一元构造可分成三个动作：

1. shift 把“模一次消失”抬高成“模 \(N^t\) 消失”；
2. suitable shift 集合给出三角格，det 是闭式；
3. LLL 短向量加 Howgrave–Graham 判据把模零转成整数零。

后面通用骨架里的 \(M_m\)、\(t_m\)、\(p_0\) 全是对这三个动作的推广。

多元为什么难

一元时自然的 shift 族是 \(x^i f(x)^j N^{t-j}\)，多元情形则没有唯一选择。给定单项式 \(\lambda\)，候选 shift

要先满足整除条件 \(\prod_j\operatorname{LM}(f_j)^{\ell_j}\mid\lambda\)，再满足支撑包含 \(\operatorname{supp}(F_{\lambda,\ell})\subseteq M_m\)。两个条件互相拉扯：\(\ell\) 越大模幂越高，但支撑越大越容易逃出 \(M_m\)。手工方法（Herrmann–May、Jochemsz–May、Boneh–Durfee）靠多项式结构挑出能用的 \(\ell\)，换一个多项式结构就得重新挑。

Algorithm 2 对每个 \(\lambda\) 枚举可行的 \(\ell\)，选取使 \(\langle\mathbf{e},\ell\rangle\) 最大者。Equation (3) 还允许各同余使用不同的 \(e_j\)，而 Meers–Nowakowski 的 Automated Coppersmith 固定 \(t_m=m\)。³

高模幂同余来自理想幂。若原始同余为 \(\tilde f_i\equiv0\pmod M\)，且 \(I=\langle\tilde f_1,\dots,\tilde f_s\rangle\)，则 \(I^q\) 中任意多项式在公共根处都模 \(M^q\) 为零。MIHNP 4/5 样本中的 \(f_{1234}\equiv0\pmod{M^2}\) 即由此得到；equation (3) 的不同模幂记录了消元产物的代数结构。

一元构造容易给人一种错觉：shift family 只是“照公式列出来”的技术细节。到了多元，这一步其实已经是组合优化。每个 \(\lambda\) 都携带一份有限预算：它在各个坐标方向上离 \(M_m\) 的边界还有多少余量。选择 \(\ell_j\) 等于决定使用多少次 \(f_j\)；收益是模幂权重 \(e_j\)，成本是支撑在各个 facet 方向上的扩张。手工 attack 中常见的 \(x\)-shift、\(y\)-shift、mixed shift，本质上是在凭经验解这个预算分配问题。

这一观察也解释了为什么项序不是一个无害的表示选择。改变 \(\prec\) 会改变 \(\operatorname{LM}(f_j)\)，进而改变“先除掉哪个指数、乘方后支撑向哪里扩张”。同一个多项式、同一个 \(P\)，仅换 leading monomial 就可能得到另一套 \(\Delta_t(f_j)\) 和另一条渐近界。后面的 LCG 例子会把这种差异算成 \(1/2-1/k\) 与 \(1/3\) 的差距。

我读到这里时联想到 Gröbner fan：一个理想在不同权重向量下有不同 initial ideal，Automated Coppersmith 也在项序切换时改变其可行 shift 几何。但二者不能直接等同。这里优化的是给定 generators 的支撑与 leading monomial，论文没有在整个 Gröbner fan 上搜索，也没有用 ideal 等价变换消掉生成元选择的影响。项序仍然是调用方提供的外部知识。

Coppersmith 的骨架：从 shift 族到行列式条件

shift 多项式与 feasible exponent vectors

monic 与 \(0\in A(f_j)\) 两个条件在这里各有用处：monic 保证 \(\operatorname{LM}\) 系数是 1，suitable set 的对角元才能是 1；\(0\in A(f_j)\) 保证 \(\ell=0\) 永远可行，且 Lemma 7 里 \(\beta-\alpha(\ell)\in\mathbb{Z}_{\ge0}^k\) 的整除条件成立。

对每个单项式 \(\lambda\in M_m\) 与指数向量 \(\ell=(\ell_1,\dots,\ell_n)\in\mathbb{Z}_{\ge 0}^n\)，如果 \(\prod_j \operatorname{LM}(f_j)^{\ell_j}\mid \lambda\)，定义候选 shift

如果还有 \(\operatorname{supp}(F_{\lambda,\ell})\subseteq M_m\)，就称 \(\ell\) 对 \(\lambda\) feasible，全体记作 \(S_m(\lambda)\)。每个 \(\lambda\) 取使加权指数最大的 feasible vector：

再取全局最大值 \(t_m:=\max_{\lambda\in M_m}r_m(\lambda)\)。最终为 \(\lambda\) 选出的 shift 是

这样构造的 \(\mathcal{G}_m=\{g_\lambda\}_{\lambda\in M_m}\) 是一个 \((M_m,\prec)\)-suitable set：每个 \(g_\lambda\) 的支撑都落在 \(M_m\)，其首项单项式恰好是 \(\lambda\)，首项系数为 1。这一点是后面“格基三角化”的全部原因。

suitable set 给出三角格

把 \(g_\lambda(x_1X_1,\dots,x_kX_k)\) 的系数向量按 \(M_m\) 的单项式顺序排成行，列也按同一顺序索引，就得到 Coppersmith 格 \(L_m\)。suitability 保证每个 \(\lambda\) 只出现一次对角线首项，因此基矩阵是三角阵。把行、列都按 \(\prec\) 升序排：\(g_\lambda\) 的支撑全在 \(\preceq\lambda\)，对角元又是 1，所以第 \(\lambda\) 行在 \(\lambda\) 列右侧全是 0。行列式不需要任何行变换，直接等于对角元乘积。行列式可以直接写成

其中

定义 \(p_0(m):=\sum_{\lambda\in M_m}r_m(\lambda)\) 后，有恒等式 \(p_M(m)=t_m|M_m|-p_0(m)\)——对每个 \(\lambda\)，模数指数贡献 \(t_m\)，扣掉该处实际用掉的 \(r_m(\lambda)\)，剩下的就是补到 \(M^{t_m}\) 的差额。这三个量分别是“变量指数总权重”“模数指数总权重”与“shift 用掉的总模数幂”。

这组记号值得停一下。\(p_j(m)\) 只看 \(M_m\) 的几何形状，与输入多项式无关；它统计第 \(j\) 个坐标在所有格点上的一阶矩。\(p_0(m)\) 才把多项式支撑、项序和模幂权重带进来。于是小根界的左边是“区域本身要付出的变量缩放成本”，右边是“该区域允许 shift 提取出的模幂收益”。Theorem 4 最后出现两个积分，并非偶然的解析技巧，而是这两类总量在大尺度下各自变成体积分。

\(r_m(\lambda)\) 是逐点最优，\(p_0(m)\) 是把所有逐点最优值加起来。这里没有跨 \(\lambda\) 的资源竞争：为一个单项式选择更大的 \(\ell\)，不会消耗另一个单项式的额度。因此 Algorithm 2 能逐个 \(\lambda\) 独立最大化，并由 suitable set 的三角结构把这些局部选择拼成全局行列式。这是自动化成立的结构性原因。如果格基不再要求“一行对应一个 leading monomial”，或者允许跨行组合后再共同优化，问题就不会这样分解。

Key Observation. 论文所谓 fixed \(M_m\) 下的 optimal，是对这类 suitable shift 选择而言的：每个 \(\lambda\) 选最大 \(r_m(\lambda)\)，于是 \(p_0(m)\) 最大、行列式中的 \(M\) 代价最小。它不是对所有可能的 Coppersmith lattice、所有基变换或所有单项式集合的全局最优性声明。

Howgrave–Graham 到渐近界

Howgrave–Graham. 设 \(g\) 至多有 \(\omega\) 个非零单项式。若 \(g(x^{(0)})\equiv 0\pmod N\)，且缩放范数满足 \(\|g(x_1X_1,\dots,x_kX_k)\| \lt N/\sqrt{\omega}\)，则 \(g(x^{(0)})=0\) 在整数上成立。⁴

每个 \(g_\lambda\) 在 \(x^{(0)}\) 处模 \(M^{t_m}\) 为零。LLL 给出的短向量配合 Howgrave–Graham 判据，可以让若干辅助多项式在整数上同时消失。要同时拿到 \(k\) 个辅助多项式，论文用的是带 \(1/(\dim(L)+1-k)\) 指数的条件：

两边取 \(\dim(L)+1-k\) 次方，再代入 \(\dim(L)=|M_m|\)：常数因子在 \(M\) 足够大时全部收进 \(\varepsilon\)，模数的有效指数变成 \(t_m(|M_m|+1-k)=t_m|M_m|-(k-1)t_m\)。忽略常数因子后，可解条件在 \(M\) 足够大时简化成

代入行列式并消去 \(M^{\,t_m|M_m|}\)，得到

渐近分析因此归结为 \(p_j(m)\)、\(p_0(m)\) 与 \(t_m\) 的阶数估计。

这里第一次出现“渐近分析把有限常数吞掉”的动作。LLL 的 \(2\)-幂因子、\(\sqrt{\dim(L)}\) 和为得到 \(k\) 个短向量付出的 \((k-1)t_m\)，最后都进入低阶项或 \(\varepsilon\)。当 \(m\) 与 \(M\) 一起进入理论极限时，这样处理是标准的；固定一个 256-bit 模数、取 \(m=2\) 或 \(3\) 时，它们却可能决定一次规约能否过 HG 阈值。

因此，渐近指数更适合回答“这套 shift 几何有没有希望优于旧构造”，不直接回答“该用 \(m=4\) 还是 \(m=5\)”“BKZ 是否比 LLL 更合适”或“这一维格在当前机器上能不能规约”。有限攻击中通常还要在两种趋势之间取平衡：

• 增大 \(m\) 使格点求和更接近积分，理论指数更可信；
• \(|mP\cap\mathbb Z^k|\) 同时按 \(m^k\) 增长，格维数和规约成本迅速上升；
• 更大的格可能提供更短的向量，也可能让数值规模、内存和求根阶段先失控；
• Assumption 1 与“能找到足够多短向量”不是同一件事，前者关心理想维数，后者关心范数。

论文的 Table 2 正好显出这条裂缝。MIHNP 3 样本从 \(m=2\) 的 27 维增长到 \(m=4\) 的 125 维，运行时间从 0.15 秒升到 94.73 秒；渐近公式本身没有变化。指数是一个方向性的极限对象，成本却由有限维格的具体形状支配。

Critical Reading. “常数吸收到 \(\varepsilon\)”不能成为有限参数实验的解释。若文章讨论的是理论界，可以省略这些常数；若讨论实际攻击，必须重新检查 LLL/HG 的原始不等式。本文后半把两个层次分开记录。

把 shift 选择重写成一个 LP

把每个 \(r_m(x^\beta)\) 写成一个整数线性规划，再缩放成只依赖连续点 \(x\in P\) 的线性规划。

从 support containment 到 J-set

对 \(\ell\in\mathbb{Z}_{\ge 0}^n\)，记

cancellation-free 条件保证 \(A(f_1^{\ell_1}\cdots f_n^{\ell_n})=\ell_1A(f_1)+\cdots+\ell_nA(f_n)\)，于是候选 shift 的指数集是

定义

其中 \(B_m=mP\cap\mathbb{Z}^k\) 是 \(M_m\) 的指数集。立即得到等价关系：

Lemma 7. \(\ell\in S_m(x^\beta)\) 当且仅当 \(x^\beta\in J_\ell^{(m)}\)。

若 \(\ell\in S_m(x^\beta)\)，候选 shift 的指数集为 \(\beta-\alpha(\ell)+A(\ell)\)，因此包含关系成立。反过来，若 \(x^\beta\in J_\ell^{(m)}\)，由 \(0\in A(\ell)\) 得 \(\beta-\alpha(\ell)\in B_m\subseteq\mathbb{Z}_{\ge0}^k\)，等价于整除条件 \(x^{\alpha(\ell)}\mid x^\beta\)；其余条件仍是支撑包含。可行性由指数集包含完整刻画，下一步将其线性化。

Lemma 7 看起来只是在改写定义，实际完成了一次关键降维：从“构造并展开多项式”降到“比较有限个指数点”。系数在这里消失了，乘法变成 Minkowski sum，整除变成指数向量的逐坐标比较。后面的 LP 之所以可能，不是因为线性规划能直接理解多项式，而是 cancellation-free 先把多项式乘法压成了支撑集合的加法。

代价也出现在同一个位置。若乘积中发生 cancellation，真实支撑可能比 Minkowski sum 小。用 \(\ell_1A(f_1)+\cdots+\ell_nA(f_n)\) 替代真实支撑时，会把某些本来可行的 shift 判成不可行；更危险的是，如果实现和证明对支撑的方向约定不一致，也可能错误地接受 shift。论文选择直接假设 cancellation-free，使等号成立，避开了“系数相消如何随 \(\ell\) 变化”的问题。

这个假设比“输入多项式看上去没有特殊系数”强。它要求对所有非负指数向量 \(\ell\) 都没有支撑塌缩。有限层 Algorithm 2 可以真的乘出 \(f_1^{\ell_1}\cdots f_n^{\ell_n}\) 再看支撑，因此不依赖该假设；渐近层不能枚举无穷多个 \(\ell\)，才需要一个统一的组合描述。换言之，cancellation-free 是从有限算法过渡到闭式渐近分析时付出的价格，不是 Coppersmith 方法本身的必要条件。

这里还可以联想到 tropicalization 或 Newton polytope 中常见的“只保留 valuation/support”操作。它们都主动丢掉系数，把代数问题投影到组合几何；投影后得到的结构更容易计算，但系数导致的退化必须另行排除。本文选择 exponent support 而不是完整 Newton polytope，是因为 suitable 条件要求每个具体单项式都留在 \(M_m\)，仅知道凸包还不够。

逐点 ILP 与缩放 LP

把 \(P\) 写成不等式描述 \(P=\{x\in\mathbb{R}^k\mid \langle a_t,x\rangle\le b_t,\ \forall t\in T\}\)，则 \(mP\) 的约束是 \(\langle a_t,x\rangle\le mb_t\)。对每个 facet \(t\) 与每个 \(f_j\)，定义支撑相对首项的“凸偏移”：

因为 \(\alpha_j\in A(f_j)\)，恒有 \(\Delta_t(f_j)\ge 0\)。max 在 Minkowski 和上可逐项分离：任意 \(u\in A(\ell)\) 都写成 \(u=\sum_j\ell_ju_j\)（\(u_j\in A(f_j)\)），于是

两边对 \(u\) 取最大，右边每个 \(j\) 独立，得到

cancellation-free 在这里的作用和 J-set 里一样：它保证 \(A(f^\ell)=\ell A(f)\)，Minkowski 和不塌缩；如果塌缩（\((1+x)(1-x)\) 就是反例），用 Minkowski 和替代真实支撑会低估可行性。逐点取最大后，可行性约束变成线性不等式，于是 \(r_m(x^\beta)\) 是一个 ILP：

把 \(\beta\) 与 \(m\) 同时缩放：令 \(x=\beta/m\)，把整数变量 \(\ell\) 换成连续变量 \(\tau\)，就得到定义在 \(P\) 上的 LP

这个 LP 对每个 \(x\in P\) 都有最优解。首先，\(\tau=0\) 可行。其次，\(P\) 的有界性保证每个坐标方向都受某个 facet 约束：固定 \(j\)，取支撑中的 \(u_j\ne\alpha_j\)。若所有 facet 都满足 \(\langle a_t,u_j-\alpha_j\rangle\le0\)，则从 \(P\) 内任一点沿 \(u_j-\alpha_j\) 出发的射线仍位于 \(P\)，与有界性矛盾。因此存在 \(t_j\) 使 \(\Delta_{t_j}(f_j)>0\)，该约束给出 \(\tau_j\) 的上界，目标函数有界。

整数解与连续解之间只差一个逐分量 floor。精确的夹逼是

直观地说：\(\varphi_P(x)\) 是在点 \(x\) 处“每单位 \(m\) 能压进去多少加权 shift 指数”，floor 造成的总损失至多 \(\sum_j e_j\)，与 \(m\) 无关。

上界来自缩放：ILP 的可行解 \(\ell\) 除以 \(m\) 后，就是 LP 在 \(\beta/m\) 处的可行解，因此 \(\langle\mathbf{e},\ell\rangle=m\langle\mathbf{e},\ell/m\rangle\le m\varphi_P(\beta/m)\)。下界取 LP 最优解 \(\tau^*\)，令 \(\ell_j=\lfloor m\tau_j^*\rfloor\)。由于 \(\Delta_t(f_j)\ge0\)，逐分量向下取整只会减小约束左端，所以 \(\ell\) 仍是 ILP 可行解；\(\lfloor z\rfloor\ge z-1\) 给出至多 \(\sum_je_j\) 的损失。该 \(O(1)\) 误差与 \(m\) 无关，求和后为 \(O(m^k)\)。

这个 rounding argument 比一般 ILP relaxation 强得多。通常把整数规划松弛成 LP，会担心 integrality gap 随实例规模增长；这里逐坐标 floor 就足够，而且损失上界与 \(m\) 无关。原因有两个：

1. 所有变量都非负，所有 \(\Delta_t(f_j)\) 也非负，向下取整不会破坏可行性；
2. 目标函数是固定的 \(\langle\mathbf e,\tau\rangle\)，变量个数 \(n\) 不随 \(m\) 增长，因此每个坐标损失不到 \(e_j\)，总损失只是 \(\sum_j e_j\)。

第二点常被忽略。这里的极限让多胞体 \(mP\) 变大，但同余多项式的数量 \(n\) 固定。如果让方程数量也随 \(m\) 增长，\(\sum_j e_j\) 就未必还是 \(O(1)\)，Lemma 9 的误差分析需要重做。论文的 LCG 应用允许方程数量随应用参数 \(k\) 改变，但对每个固定 \(k\) 再取 \(m\to\infty\)；两个极限没有交换。

我觉得这一步最能说明 LP 不是一种“近似算得快”的替代品。对单个 \(\beta\)，它确实把整数约束放松了；但 floor sandwich 证明了它抓住 \(r_m\) 的一阶项。论文要的是 \(m^{k+1}\) 级别的总和，所有格点上的 \(O(1)\) 损失合计只有 \(O(m^k)\)，刚好低一阶。因此 LP 丢掉的是会在极限中消失的离散锯齿，而不是主导渐近界的部分。

Quick Check. 若某个 \(\Delta_t(f_j)\) 为负，floor 后约束左端反而可能增大，这个论证立即失效。定义中取 \(u=\alpha_j\) 可得 \(\Delta_t(f_j)\ge0\)，所以 leading monomial 本身不仅用于整除，也在 rounding proof 中提供了单调性。

对偶、piecewise affine 与积分

把 LP 写成矩阵形式 \(\max \mathbf{e}^\top\tau\) s.t. \(\Delta\tau\le b-Ax,\ \tau\ge 0\)。它的对偶是

对偶可行域

不依赖 \(x\)：它只由 \(\Delta\) 与 \(\mathbf{e}\) 决定，是一个固定的有理多面体，顶点有限。由强对偶与“最优解可取在顶点”：

其中每个 \(L_i(x)=(b-Ax)^{\top}z^{(i)}\) 是仿射函数。取最小值会把 \(P\) 切成有限个满维单元格 \(Q_i\)，在每个 \(Q_i\) 上 \(\varphi_P=L_i\)，即 Theorem 2 的分片仿射结构。

单元格定义为 \(C_i=\{x\in P\mid L_i(x)\le L_h(x)\ \forall h\}\)。每个差 \(L_i-L_h\) 都是仿射函数，因此 \(C_i\) 是有理多胞体；有限个 \(C_i\) 覆盖 \(P\)。去重后的两个仿射函数不可能在开集上相等，所以满维单元格的内部互不相交；低维面仅在边界上重复计数，不贡献体积。

对偶变量 \(z_t\) 可以读成 facet 约束的 shadow price。原问题在点 \(x\) 处有余量 \(b-Ax\)：点越靠近某个 facet，这个方向能容纳的支撑扩张越少。一个对偶顶点 \(z^{(i)}\) 给出一组给 facet 定价的方法，\(L_i(x)=(b-Ax)^\top z^{(i)}\) 是按这组价格计算的最大 shift 收益上界。强对偶说明至少有一组价格把上界压到真实最优值。

于是 \(\varphi_P\) 是有限个仿射函数的逐点最小值。它因此是 concave、piecewise affine 的；cell 边界对应两套对偶证书同时最优。原来随每个格点重新求解的 shift optimization，被压缩成“先枚举有限个对偶顶点，再判断 \(x\) 落在哪个 cell”。这与 parametric linear programming 的标准图景完全一致：参数只进入右端项，optimal basis 在参数空间的不同区域内保持不变。

这给我一个比公式更直观的画面。记归一化位置为 \(\xi=\beta/m\)。让 \(\xi\) 在 \(P\) 内移动，相当于把 leading monomial \(\lambda=x^\beta\) 放到单项式区域的不同位置。靠近某个边界时，可用的 shift 会先在对应 facet 方向耗尽；跨过 cell 边界后，限制最紧的 facet 组合发生变化。Piecewise affine 不是实现技巧，而是“哪一组边界正在卡住 shift”发生离散切换的记录。

低维 cell 被丢弃也需要分清两种语境。对积分而言，它们测度为零，不影响 \(\sigma_0\)；对有限 \(m\) 的格点枚举而言，边界上仍可能有 \(O(m^{k-1})\) 个点。这些点不能从 Algorithm 2 中删掉，只是在 \(m^{k+1}\) 归一化后贡献低一阶。Algorithm 1 过滤低维 cell，是在计算主项，不是声称边界上不存在 shift。

剩下的积分由 Ehrhart 理论处理。对 affine \(L\)，加权格点计数有

这条估计的来路是 weighted Ehrhart quasi-polynomial（论文 Lemma 6）：对一次项有

常数项则是普通 Ehrhart 计数 \(m^k\int_Q1\,dx+O(m^{k-1})\)。合起来除以 \(m\) 再相加，就是 Corollary 1。逐 cell 求和时，落在 cell 边界上的格点会被重复计入；边界是有限个 \((k-1)\) 维有理多胞体的并，这样的格点数至多 \(O(m^{k-1})\)，误差等级不变。

Ehrhart 理论在这里承担的是“离散求和变连续积分”的合法性。单纯写 Riemann sum 直觉还不够，因为 \(P\) 是有理多胞体，格点数随 \(m\) 带有周期波动；\(\varphi_P\) 又在不同 cell 上使用不同仿射式。Weighted Ehrhart quasi-polynomial 精确描述了这些波动：最高次项只由体积与积分决定，周期性留在低次系数中。

这也解释了 Meers–Nowakowski 插值路线为何会遇到 period。若直接把 \(p_0(m)\) 当 quasi-polynomial 重建，就必须知道或猜到周期，并为每个 residue class 收集足够多样本。LP 路线没有让 quasi-polynomial 消失；它绕过了重建整个函数，只取最高次系数。对渐近界来说，低阶周期项本来就会被除掉，因此先算完整 quasi-polynomial 再取 leading coefficient，信息量过剩。

Appendix A 证明 \(p_0(m)\) 最终是 quasi-polynomial，因此 LP 结果与旧插值路线处理的是同一个离散函数。区别在计算路线：一个从大量有限 \(m\) 值反推函数，另一个从 parametric LP 和几何积分直接读出 leading term。

Lemma 9 两边对 \(\beta\in mP\cap\mathbb{Z}^k\) 求和，第一项给出 \(m\sum_\beta\varphi_P(\beta/m)\)，误差项是 \(O(|mP\cap\mathbb{Z}^k|)=O(m^k)\)；Corollary 2 再把求和换成积分。于是由 Lemma 9 的夹逼与 \(|mP\cap\mathbb{Z}^k|=O(m^k)\)：

同理 \(p_j(m)=m^{k+1}\int_P x_j\,dx+O(m^k)\)。而 \(t_m=O(m)\)，所以 \((k-1)t_m\) 被 \(m^{k+1}\) 支配。汇总就是主定理：

Theorem 4. 对满维有理多胞体 \(P\subseteq\mathbb{R}_{\ge 0}^k\) 与 \(M_m=\{x^\beta\mid\beta\in mP\cap\mathbb{Z}^k\}\)，Automated Coppersmith 的渐近界系数为 \(\sigma_j=\int_P x_j\,dx\ (1\le j\le k)\) 与 \(\sigma_0=\int_P\varphi_P(x)\,dx\)。对任意足够小的 \(\varepsilon>0\)，可恢复的小根界满足 \(\prod_{j=1}^{k}X_j^{\sigma_j}\lt M^{\sigma_0-\varepsilon}\)。

实现里要算的就是这三样：\(\sigma_j\) 是多胞体矩，\(\sigma_0\) 是 LP 最优值函数的积分，而最优值函数本身由有限个对偶顶点给出。

我怎样理解 Theorem 4

Theorem 4 的证明在论文里很短，因为真正的工作已经分散在 Theorems 1–3 和 Lemma 9 中。把依赖关系展开后，结论需要同时用到：

• \(p_j(m)\) 的格点一阶矩以 \(m^{k+1}\int_Px_j\) 为主项；
• \(r_m(x^\beta)\) 与 \(m\varphi_P(\beta/m)\) 之间只有 \(O(1)\) 误差；
• \(\varphi_P\) 是有界的分片仿射函数，可以逐 cell 做 weighted Ehrhart 求和；
• \(t_m=O(m)\)，因此 \((k-1)t_m/m^{k+1}\to0\)。

最后一条看似最弱，却负责把“需要 \(k\) 个辅助多项式”的额外代价从主项中消掉。它只说明这个代价在渐近指数里不可见，不说明有限格中一定能得到代数独立或生成零维理想的辅助多项式。Assumption 1 仍然留在 Theorem 4 之外。

还可以检查 \(P\) 的整体缩放。把 \(P\) 换成 \(cP\) 时，\(\sigma_j=\int_Px_j\) 按 \(c^{k+1}\) 缩放；在相应的齐次结构下，\(\sigma_0\) 也按同阶缩放。界

两边主指数同时乘同一因子，等界情况下的比值 \(\delta=\sigma_0/\sum_j\sigma_j\) 不变。论文因此强调 shape 而不是 size。调大 \(P\) 只是在有限层改变格维数与取样密度，不能凭空改善渐近指数；真正有用的是改变 facet 方向和相对位置。

Critical Reading. Theorem 4 是 conditional exactness：给定满足假设的 \(P\)、支撑和项序，系数公式是精确的；输入 \(P\) 是否是好选择仍没有全局算法。后面 §3.4 从 Newton-type polytopes 提取法向量，是另一层启发式。把两层混在一起，就会把“精确计算一个候选”误写成“精确找到最优候选”。

Algorithm 1 怎么算成精确有理数

对偶顶点与满维单元格

asymptotic.py 基本是对 Algorithm 1 的逐行翻译：

1. _paper_hrep 把 Sage Polyhedron 的 A_ineq 形式转成 \(\langle a_t,x\rangle\le b_t\)；
2. _delta_matrix 逐 facet、逐 congruence 计算 \(\Delta_t(f_j)\)；
3. _dual_vertices 构造 \(Y=\{\Delta^\top z\ge e,\ z\ge 0\}\) 并枚举有理顶点；
4. _affine_forms 从每个顶点造 \(L_i=(b-Ax)^\top z^{(i)}\)，去重排序；
5. _full_dimensional_cells 对每个 \(i\) 取 \(P\cap\bigcap_h\{L_i\le L_h\}\)，只保留 \(\dim=k\) 的单元格；
6. verify_cell_coverage 校验单元格互不重叠且体积相加等于 \(\operatorname{vol}(P)\)；
7. integrate_affine 对每个单元格与每个坐标轴积分。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from sage.all import Polyhedron, PolynomialRing, QQ, ZZ
from autocopper import Congruence, asymptotic_bound

R = PolynomialRing(ZZ, names=("x",))
x = R.gen()
P = Polyhedron(vertices=[(0,), (1,)], base_ring=QQ)

bound = asymptotic_bound(
    P,
    [Congruence(x + 1)],
    assume_cancellation_free=True,
)

assert bound.variable_coefficients == (QQ("1/2"),)
assert bound.modulus_coefficient == QQ("1/2")

返回值还包含精确的 \(\Delta\) 矩阵、对偶顶点、仿射形式与满维单元格。实现不依赖 LattE；积分由多胞体三角剖分与单纯形体积完成。

三角剖分上的精确仿射积分

对满维单纯形，体积为顶点差矩阵行列式的绝对值除以 \(k!\)：

仿射函数在单纯形上的积分等于体积乘以顶点值的平均：

用重心坐标写 \(x=\sum_i\lambda_i v_i\)，其中 \(\lambda_i\ge0\)、\(\sum_i\lambda_i=1\)。仿射函数满足 \(L(x)=\sum_i\lambda_iL(v_i)\)，而 \(\int_S\lambda_i\,dx=\operatorname{vol}(S)/(k+1)\)，代入即得上式。

两步都只用 QQ 的精确有理运算，所以 \(\sigma_j,\sigma_0\) 是精确分数，而不是浮点近似。

一元 worked example 与 Appendix C 数值

取 \(f=x+1\)、\(P=[0,1]\)。\(A(f)=\{0,1\}\)，\(\alpha=(1,)\)。\(P\) 的两个 facet 是 \(-x\le 0\) 与 \(x\le 1\)，代入

分别得到 \(1\) 与 \(0\)。LP 变成 \(\max\tau\) s.t. \(\tau\le x\)，即 \(\varphi_P(x)=x\)。于是

对偶是 \(\min xz\) s.t. \(z\ge1,\ z\ge0\)，顶点只有 \(z=1\)，所以 \(L(x)=x\)，整个 \([0,1]\) 是一个 cell。于是

有限层给出同一结果。对 \(\beta=0,\dots,m\)，\(S_m(x^\beta)=\{0,\dots,\beta\}\)，所以 \(r_m(x^\beta)=\beta\)，\(p_0(m)=p_1(m)=m(m+1)/2\)，\(t_m=m\)，\(p_M(m)=m(m+1)/2\)；除以 \(m^2\) 后均收敛到 \(1/2\)。回归测试还检查了收敛方向：\(m=4\) 时 \(\sum r=10>16/2=8\)，有限层从上方逼近 \(\sigma_0\)。API 输出 sigma_x=1/2 sigma_0=1/2 cells=1。

更不平凡的是 Appendix C 的四个支撑例子（\(P=[0,1]^2\)、\(\mathbf{e}=(1,1)\)、deglex with \(y\prec x\)）。仓库回归测试独立重算出精确 \(\sigma_0\)：

表里四个分数我都在本机重跑过，与仓库断言一致。Exp. 4 解释了为什么启发式插值会失效：\(p_0\) 的 quasi-polynomial 周期是 52，插值必须把 \(m\) 推到 157，此时 \(|M_m|=24964\)，单项式逐个枚举要跑 35 分钟；而 LP 路线在同一例子上亚秒完成。论文 Table 3 记录的就是这个差距。¹

这里的“精确”需要限定对象。实现能精确表示 \(P\) 的有理顶点、对偶顶点、仿射系数、cell 交集和积分结果，因此不会因为浮点误差把两个很接近的 cell 边界分错，也不会把 \(499/2400\) 截成一个难以追溯的小数。这个 exactness 对审计 Algorithm 1 很有价值。

它不等于：

• 选到全局最优的 \(P\)；
• 证明有限参数下 LLL 一定找到目标短向量；
• 证明辅助多项式理想必为零维；
• 证明论文给出的十进制 \(\theta\) 是真实连续最优点；
• 证明 unit-coefficient 代表多项式与原密码方程在根恢复阶段等价。

最后一点尤其容易混淆。Algorithm 1 只读取支撑、leading monomial 和模幂指数，所以用全 1 系数多项式复现渐近系数是合法的；Algorithm 2 和端到端求根会实际计算多项式值，系数当然不能随便换。当前 paper_applications.py 复现的是 Section 4 的 asymptotic geometry，不是五个密码系统的完整 attack。

我把 Algorithm 1 看成一种小型 proof-producing computation：返回的不只是 \(\sigma_0\)，还包括 \(\Delta\)、对偶顶点、每个 cell 的仿射式和覆盖检查。若只打印最后一个小数，前面的可审计结构就浪费了。理想的复现报告应该能回答“哪个对偶顶点在哪个区域最优”“各 cell 的积分是多少”“体积是否完整覆盖 \(P\)”。

P 从哪里来

Newton-type polytopes

小根界主要取决于 \(P\) 的形状而非大小，但“在所有有理多胞体上优化”不可行。论文 §3.4 的启发式是让候选 facet 法向由输入多项式自己给出：

收集两者的 primitive outward facet normals 作为候选方向 \(\mathcal{N}\)。把一部分方向固定成常数，另一部分设成可调参数 \(\theta\)，得到参数族

对偶可行域 \(Y\) 与 \(\theta\) 无关，因此 \(\varphi_{P(\theta)}\) 可以保留参数作符号计算。参数积分仍然复杂：CIHNP 的三参数情形分成 102 个分支，论文改用有界域上的有限精度数值优化。

原因在定义里：\(Y=\{\Delta^\top z\ge e,\ z\ge0\}\) 只依赖每个 facet 的法向 \(a_t\)（通过 \(\Delta_t(f_j)\)）和模数指数 \(\mathbf{e}\)，不依赖常数项 \(b_t\)。参数 \(\theta\) 只改 \(b_t\)，所以对偶可行域不动；变的是仿射形式 \(L_i(x)=(b(\theta)-Ax)^\top z^{(i)}\)，也就是单元格的切法。

参数化多胞体与精确有理网格

实现没有照搬“有限精度数值优化”，而是把它改成确定性的精确有理网格搜索，保证结果可复现、可审计：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from autocopper import parameterized_polytope, rational_grid_search

P = parameterized_polytope(
    dimension=2,
    fixed_constraints=[((0, 1), 1)],
    parameter_normals=[(1, -2)],
    parameters=(QQ(1) / 2,),
)

result = rational_grid_search(
    [QQ(n) / 500 for n in range(280, 330)],
    lambda point: liph_x1_exponent(liph_bound(point[0])),
)

rational_grid_search 逐个求值并返回 best_parameters、best_value 与完整求值记录。LIPH 的精确最优参数 \(\theta^*=(2\sqrt{223}-10)/33\) 是无理数；精细网格找到 \(301/500\)，与闭式最优值的距离小于 \(10^{-3}\)，指数误差小于 \(10^{-4}\)。参数间距显式控制离散化误差，所有中间值仍保留为有理数。

对 \(P\) 选择的保留意见

论文最强的措辞是 systematic、non-heuristic，但这个描述只适用于“固定 \(P\) 后计算渐近系数”。Section 3.4 明确承认，在所有有理多胞体中找最优形状不可行，于是从 \(P^\cup\) 与 \(P^\Sigma\) 的 facet normals 构造一个低维参数族。法向量集合来自输入支撑，这个选择有很强的几何动机，却没有完备性：真正更优的 \(P\) 可能需要新的 facet 方向。

即使固定法向量，参数积分仍会产生复杂的 piecewise polynomial。CIHNP 三个参数已经分成 102 个区域，论文转而在有界域上做有限精度数值优化。实现把它改成有理网格后，提高的是可复现性：每个候选点的结果精确、搜索轨迹可保存。网格本身仍只覆盖离散点，除非另有闭式导数、区间界或 exhaustive cell analysis，不能把网格最优写成连续全局最优。

这层启发式并不削弱 Theorem 4，反而说明 theorem 和 search 应该有两个接口：

1. asymptotic_bound(P, \dots)：对给定 \(P\) 返回可审计的精确系数；
2. search_polytope(family, domain, \dots)：在一个明确声明的候选族和搜索精度内找较好参数。

如果两者混成一个 auto 按钮，用户很难知道最终小数的证书覆盖到哪里。当前实现让网格搜索单独返回完整记录，是一个比“优化器吐出 best value”更适合研究复现的选择。

还有一个实践上的反直觉：更复杂的 \(P\) 未必更好。增加 facet 可能改善 \(\sigma_0/\sum\sigma_j\)，也会增加 \(|T|\)、对偶多面体 \(Y\) 的顶点数和 cell 数，Algorithm 1 的组合复杂度随之上升；有限层的 \(mP\cap\mathbb Z^k\) 也可能变得更难枚举。论文 Remark 8 报告复杂形状通常只带来边际收益，这是一条实验观察，不是一般定理。

Algorithm 2：有限参数下的 shift 选择

渐近层只需要连续 LP；真正攻击一个具体模数时，需要 Algorithm 2 枚举有限 shift：

1. 对每个 \(\lambda\in M_m\) 枚举满足整除条件与支撑条件的 \(\ell\)；
2. 选使 \(\langle\mathbf{e},\ell\rangle\) 最大的 \(\ell^\lambda\)，记录 \(r_m(\lambda)\)；
3. 取 \(t_m=\max_\lambda r_m(\lambda)\)；
4. 输出 \(g_\lambda=M^{t_m-r_m(\lambda)}F_{\lambda,\ell^\lambda}\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

from sage.all import PolynomialRing, ZZ
from autocopper import Congruence, select_shifts

R = PolynomialRing(ZZ, names=("x",))
x = R.gen()

family = select_shifts(
    [(0,), (1,), (2,)],
    [Congruence(x + 1)],
    modulus=17,
)

assert family.t == 2
assert [item.shift for item in family.selections] == [
    R(17**2),
    17 * (x + 1),
    (x + 1) ** 2,
]

这是论文 Appendix D Example 1。对 \(\lambda=1\)，任意 \(\ell\ge1\) 都有 \(\operatorname{LM}(f)^\ell=x^\ell\nmid1\)，故只能取 \(\ell=0\)。对 \(\lambda=x\)，\(\ell=0\) 给出 \(F=x\)，\(\ell=1\) 给出 \(F=f=x+1\)，两者的支撑都包含在 \(M_m\) 中，故选择 \(\ell=1\)。对 \(\lambda=x^2\)，\(\ell=2\) 时 \(F=f^2\) 的支撑恰为 \(M_m\)，而 \(\ell\ge3\) 时支撑超出 \(M_m\)。相应选择如下：

缩放后的格基是

对角元乘积是 \(M^2\cdot MX\cdot X^2=M^3X^3\)，与闭式 \(\det=M^{p_M}X^{p_1}\) 一致：这里 \(p_M=3\)、\(p_1=3\)。实现仍需单独验证行列式；一旦出现支撑外单项式，三角结构便不再成立。

实现里的 _verify_suitable 会再检查三件事：每个 shift 的支撑不逃出 \(M_m\)、首项单项式与选中指数一致且系数为 1、所有 leading monomial 恰好覆盖 \(M_m\)。这对应 suitable set 的三个必要条件，防止三角基被静默破坏。

Algorithm 1 与 Algorithm 2 的关系不是“同一个算法的渐近版和有限版”那么简单。Algorithm 2 操作真实多项式：枚举整数 \(\ell\)、展开乘积、检查实际支撑、输出一个具体格基。Algorithm 1 只操作支撑几何与连续极限：它不生成任何可送进 LLL 的 shift，也不知道给定 \(M\) 时该取哪个 \(m\)。

两者可以互相校验。固定一串 \(m\)，用 Algorithm 2 计算

应逐渐靠近 Algorithm 1 的 \(\sigma_j,\sigma_0\)。但收敛可能带周期振荡，且有限值可从上方或下方靠近；一元 \(f=x+1\) 在 \(m=4\) 时 \(p_0/m^2=10/16>1/2\) 就是上方逼近。单个小 \(m\) 的数值比渐近系数更大，不表示有限攻击突破了理论界，只是低阶项尚未消失。

Implementation Note. Suitable verification 是一张局部证书：它证明当前矩阵确实具有论文用于计算行列式的三角结构。它不证明 LLL 输出质量，也不证明根恢复。把不同阶段的证书拆开，失败时才能知道是 geometry、reduction 还是 algebraic solving 出了问题。

端到端管线与护栏

缩放格、HG 筛选与 Assumption 1

auto_coppersmith 把五步接成一条链：select_shifts → build_lattice → select_auxiliaries → solve_auxiliary_system → verify_candidates。

build_lattice 的列缩放是 \(\prod_j X_j^{i_j}\)，即把 \(x^\beta\) 列乘上 \(X^\beta\)。它先验证基矩阵是方阵，再验证行列式等于 suitable-shift 对角线的闭式值：

行列式不一致时抛出 GeometryError。随后进入规约后端，实际使用的后端及其配置写入 reduction_log。

短向量按范数排序后逐个重建多项式，接受判据是缩放范数的 Howgrave–Graham 条件：

每接受一个多项式就把当前理想转成 \(\mathbb{Q}\) 上的理想并查维数。论文的 Assumption 1 要求辅助多项式生成的理想是 zero-dimensional；实现把这一假设变成显式失败：

• 没有辅助多项式通过 HG 界 → AssumptionError；
• 理想维数不是 0 → AssumptionError，绝不声称已经恢复根。

候选根还要再过 verify_candidates：坐标必须是整数、严格满足 \(|x_j|\lt X_j\)、并且逐条满足 \(f_j(x^{(0)})\equiv 0\pmod{M^{e_j}}\)。只有全部通过才进 verified_roots。

严格验证与小例子

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from sage.all import PolynomialRing, ZZ
from autocopper import Congruence, auto_coppersmith

R = PolynomialRing(ZZ, names=("x",))
x = R.gen()

result = auto_coppersmith(
    congruences=[Congruence(x - 3)],
    modulus=101,
    bounds=(10,),
    monomial_exponents=((0,), (1,), (2,)),
)

assert result.verified_roots == ((3,),)

该 smoke test 覆盖 shifts → lattice → reduction → HG → ideal → verification 的完整路径；线性同余本身仅用于保持例子最小。

RSA 已知高位的边界扫描

tests/test_rsa_known_high_bits.py 用真实 256-bit 素数构造 \(N=pq\)、已知 \(p\) 的高 64 位，把问题化成 \((A+x)(B+y)-N\equiv0\pmod N\)，然后横扫不同单项式集、项序、模指数与 \(y\) 界。README 记录的边界现象：

• square 方案恢复 64 位与 96 位泄漏；
• triangle 方案（\(\{i+j\le m\}\)）加 tight \(y\) bound 稳定到达 112 位；
• 压力测试里 \(m=12\) 在 116 位 20/20 成功，\(m=10\) 在 116 位只有偶发成功，默认扫描显示 120 位失败；
• opt-in --deep 探测 \(m=18\) 的约 190 维格：一次 probe 跨过 120 位（约 176 s），124 位则一致抛出 AssumptionError。

渐近界只给出参数方向；有限实例的恢复还取决于格维数、项序、\(y\) 的界以及 Assumption 1。

规约后端与自动回退

build_lattice 与 auto_coppersmith 接受 backend="flatter"（默认）、"sage" 或 "blaster"：

每次规约都执行 same_lattice_transform：规约前后维数、行列式一致，变换矩阵必须整值且满足 \(U\cdot B=B'\)，行列式相等保证 \(|\det(U)|=1\)。Flatter 崩溃、超时或输出形状错误时回退到 Sage，reduction_log 将实际后端记录为 sage[flatter_fallback]。

基准语料（缩放一元格 \((x+1)^k\)、单项式 \(\{1,x,\dots,x^k\}\)）上三个后端得到相同的 Hermite factor。小维度 int64 格上 BLASter 最快，大条目格上 Sage 通常最快；Flatter 有 CLI 启动开销，但可处理更大的输入。本机 2025-07-04 构建的 Flatter 曾触发 SIGSEGV，回退逻辑在测试中实际生效。

论文实验与本地测试不是同一张表

论文 Table 2 在 SageMath 10.8、Apple M2、8 GB 内存上跑了 15 组根恢复实验。维数从 11 到 165，耗时从 0.01 秒到 94.73 秒；所有列出的实例都找回正确根。这些数据支持“Assumption 1 在所选实例上可用”，但样本是作者挑选的成功参数点，不能估计失败概率，也不能推出相邻参数同样成功。

本地仓库的回归测试关注另一件事：公式和实现是否对账。test_paper_regressions.py 检查 Appendix C 分数、一元极限与 LCG 特例；test_paper_applications.py 检查 Section 4 的精确指数、参数网格以及 Appendix B 的上界实例；通用 attack test 跑一个 \(x-3\bmod101\) 的最小端到端例子。它们覆盖了大量 asymptotic machinery，却没有逐项重跑论文 Table 2 的 15 个有限格。

这种拆分是合理的：把 94 秒级、依赖格规约随机细节或外部后端的实验放进常规单元测试，会让测试又慢又脆。但写文章时必须明确“18 tests passed”证明什么。它证明若干公式、精确分数和接口行为保持不变；它不是对论文完整实验矩阵的独立复现。

我会把证据分成三档：

• algebraic regression：精确等式、支撑、积分和指数断言；
• algorithmic smoke test：完整调用链能在小例子上恢复根；
• cryptanalytic reproduction：按论文参数生成真实实例，重复有限格规约与根恢复。

当前仓库前两档较强，第三档只有 RSA known-high-bits 等自建扫描，尚未覆盖 Table 2 全表。这个差异比笼统写“测试通过”更有信息量。

五个应用的渐近界

论文把 Theorem 4 用到五个具体密码分析问题上，全部改进了已知渐近界。仓库的 examples/paper_applications.py 用 unit-coefficient 等价代表多项式（Algorithm 1 只看支撑与首项）重现了这些数，本机 SageMath 10.6 上全部断言通过：

“需泄漏”列是论文 Table 1 的口径（对应 \(1-\delta\) 的百分数）；本实现列给出可直接对账的精确有理值。运行耗时在该机上从 0.053 s 到 1.374 s 不等，与论文“秒级完成”的实验结论一致。

等界 \(X_1=\cdots=X_k=X\) 下，\(\delta\) 表示未知部分允许占据的指数比例：\(X\lt M^{\delta}\)，对应已知泄漏比例 \(1-\delta\)。MIHNP 3 样本中 \(\delta=11/24\)，因此未知低位比例小于 45.83%，等价于至少泄漏 54.17%。CIHNP 与 ECHNP 使用同一换算；LIPH 单独列出 \(X_1\) 的指数，因为 \(X_2=M^{6/17}\) 已由问题固定。

这些百分比很适合放在 Table 1，却也最容易被过度解释。首先，它们是特定变量归一化下的指数。等界假设把多维区域

投影成一条 \(X=M^\delta\)；若各变量的先验界不同，真正有意义的是原来的加权乘积，而不是单个 \(\delta\)。其次，“required leakage”还依赖如何把协议中的 bit leakage 映射到 \(X_j\)。这个映射属于上游密码建模，不由 Theorem 4 自动完成。

Table 1 说“improves previous asymptotic bounds”，应读成在对应建模、项序和候选 polytope 下找到了更强的充分条件。它没有证明旧界以下的实例不可解，也没有给出安全下界。Coppersmith attack 的失败不构成 hardness proof；换一组预处理方程、换一个 lattice construction、使用更强规约或别的代数攻击，都可能改变边界。

我对这张表的用法是：先把它当作 attack design 的筛选器。指数有明显改善时，值得继续做有限参数实验；改善只有千分位时，还要比较维数、cell 数、规约时间和根恢复稳定性。只按 \(\delta\) 排名，可能选中渐近上更好、有限层反而更难跑的构造。

从密码问题到 equation (3)

Theorem 4 不负责预处理。MIHNP 需要先用 Gröbner 消元去掉隐藏数 \(\alpha\)，得到关于误差变量的两两同余；4/5 样本还产生 degree 3、mod \(M^2\) 的同余。ECHNP 则从椭圆曲线点加关系消元，得到共享 nonce 高位与各签名低位之间的多元同余。paper_applications.py 使用支撑和首项相同的 unit-coefficient 多项式，因为 Algorithm 1 不读取其余系数。

项序与多胞体形状会改变结果

LCG 的例子最能说明问题。\(k\) 个连续输出给出

用权重 \(w_j=j(k+1-j)\) 的 weighted deglex，能保证 \(\operatorname{LM}(f_i)=x_{i+1}^2\)。这个保证可以直接算：\(x_{i+1}^2\) 的权重是 \(2w_{i+1}\)，\(x_ix_{i+2}\) 的权重是 \(w_i+w_{i+2}\)，而

其余单项式的权重更低，所以 weighted deglex 下首项稳定是 \(x_{i+1}^2\)。普通 deglex 不区分这三项，\(x_ix_{i+2}\) 会按变量序抢先成为首项，界掉到 \(M^{1/3}\)。配合单纯形 \(\sum_jx_j\le1\)，LP 的最优值函数是全局仿射的

论文 Remark 10 指出这里的对偶可行域 \(Y\) 只有一个顶点，所以 \(\varphi_P\) 全局仿射而不是分片。这两个积分是 Dirichlet 积分的特例：

其中 \(\Delta_k=\{x\ge0,\ \sum x_i\le1\}\)。取 \(a_j=1\)、其余为 0 得到 \(\sigma_j=1/(k+1)!\)；把 \(\varphi_P=(1/2)\sum_{j=2}^{k-1}x_j\) 代进去得到 \(\sigma_0=(k-2)/(2(k+1)!)\)，等界时 \(\delta=\sigma_0/(k\sigma_j)=1/2-1/k\)。于是

仓库对 \(k=4\) 做了特化：权重为 \((4,6,6,4)\)，输入两个同余，并断言 \(\sigma_j=1/120\)、\(\sigma_0=1/120\)、\(\delta=1/4\)。Automated Coppersmith 在给定单项式序与单项式集后自动选择 shift；这两项仍是外部设计参数。

LCG 例子还揭示了一个容易被“自动化”叙述掩盖的事实：人类知识被前移到了 term order。权重 \(w_j=j(k+1-j)\) 不是 Algorithm 1 搜出来的，它来自对递推关系结构的观察。这个权重让平方项 \(x_{i+1}^2\) 比交叉项 \(x_ix_{i+2}\) 恰好多 2，从而把 leading monomial 固定在有利方向。LP 在此之后精确评估该选择。

这和手工 Coppersmith 的差别不是“人不再设计，机器全做”，而是设计对象变了。过去直接设计几百个 shifts；现在设计较少的高层对象：生成元、项序、\(P\) 的法向量与参数范围。机器展开其组合后果。高层选择一旦错了，后面的精确计算只会非常精确地评估一个差的设计。

Appendix B 的全局上界

附录 B 用 layer-cake 表示给出三个方法内部的上界：

• \(f=xy+ax+by+c\) 时，任意满维 \(P\subseteq\mathbb{R}_{\ge0}^2\) 都满足 \(\delta\le1/3\)，且 \(P=[0,1]^2\) 取等；
• \(f=a_dx^d+\cdots+a_0-y\) 时，\(\delta\le1/(d+1)\)；
• 单个 total degree \(d\) 的模同余在对称等界下满足 \(\delta\le1/d\)。

证明把 \(\varphi_P\) 的超水平集平移到 \(P\) 的切片中，再比较体积并积分。仓库对三条结论均有断言覆盖；Theorem 7 的一元 \(d=3\) 用例得到 \(\delta=1/3\)，三元 \(d=2\) cube 用例得到 \(\delta=1/12\le1/2\)。

Theorem 5 的 \(1/3\) 上界可以手推。对 \(f=xy+ax+by+c\)，有

记 \(P_t=\{(x,y)\in P\mid\varphi_P(x,y)\ge t\}\)。在 \(x\ge y\) 的半区，将 \((x,y)\) 平移到 \((x,y-t)\)，像点仍位于 \(P\cap\{x-y\ge t\}\)；在另一半区使用对称平移。因此

对 \(t\) 积分并用 layer-cake 表示，得到

另一方面，\(P\subseteq\mathbb R_{\ge0}^2\) 给出 \(\varphi_P(x,y)\le\min(x,y)\)。把第一个上界取一次、第二个取两次：

而等界指数为

\(P=[0,1]^2\) 时 \(\varphi_P=\min(x,y)\)，等号成立。这个证明的意义不只在得到 \(1/3\)：它对所有满维 \(P\) 同时成立，说明继续调 polytope 已经无法突破该障碍。Section 3.4 的搜索只能在方法允许的上界内移动。若想越过 \(1/3\)，需要改变生成元、项序、预处理方程或整个 lattice ansatz，而不是再把 \(\theta\) 网格调细。

与 cuso、kiona 的边界

三个工具处理的层次不同：

Meers–Nowakowski 用 Lagrange 插值恢复 \(p_0\) 的 quasi-polynomial；Feng 等人改用 sumset 理论；Ryan 的 cuso 路线结合 Gröbner basis、图剪枝与符号预计算；Ding 等人则把渐近系数化为 LP 最优值函数的积分。^{3 5 6 7 8}

auto-copper 的自动化边界是明确的：给定单项式集 \(M_m\) 与项序后，Algorithm 2 对每个 \(\lambda\) 选择最大的 \(\langle\mathbf e,\ell\rangle\)；\(P\) 的形状与项序仍由调用方决定。Theorem 4 解决的是渐近系数的精确计算，不是任意多元小根实例的通用求解。

我把三者放在一起时，更像是在比较一条 pipeline 上的不同工具，而不是竞争同一个“最好用的 Coppersmith 包”：

• auto-copper 接近 analysis pass：输入已规范化的同余系统与 monomial geometry，输出渐近系数及其几何证书；
• cuso 接近 solver：愿意接受更宽的 relation，负责生成 shifts、规约并递归找根；
• kionactf/coppersmith 接近 attack template library：提供经典构造和后端，让使用者自己调整参数与求根策略。

这也改变了“自动化程度”的比较方式。一个工具输入更窄，不一定能力更弱；它可能在窄接口上提供更强的可证明输出。另一个工具能接更多实例，也不表示其每个 shift heuristic 都有同样的渐近证书。对研究复现，接口边界和 failure semantics 往往比“支持多少 attack”更重要。

LP 对偶还让我想到 abstract interpretation：真实有限 shift 集很大，\(\varphi_P\) 是保留主阶行为的连续抽象；Algorithm 1 在这个抽象域里精确计算。这个类比的限制也很明确——论文证明了 asymptotic coefficient 的保真性，却没有给出从任意有限失败反推抽象失真的机制。它不是一个 complete solver abstraction。

实现边界与没有覆盖的东西

三个假设

第一，asymptotic_bound 强制 assume_cancellation_free=True。渐近公式建立在 \(A(f^\ell)=\ell A(f)\) 的 Minkowski 等式上，而实现不尝试为任意输入判定该性质；\((1+x)(1-x)=1-x^2\) 是最小反例。API 因此要求调用方显式确认该假设。有限层的 Algorithm 2 逐个构造实际乘积并检查支撑，不需要此声明。

第二，Assumption 1。辅助多项式理想 zero-dimensional 是标准启发式；条件不满足时实现抛出 AssumptionError，未经模验证的候选不会进入结果。

第三，实现从 equation (3) 开始，不负责密码系统到同余系统的 Gröbner 预处理，不保证 Assumption 1，也不全局优化所有有理多胞体。

把它们写成“三个假设”仍然有些粗。沿实际 pipeline 展开，至少有五个不同的可信边界：

1. 建模边界。 原密码问题是否正确降到 equation (3)，消元有没有引入赘根，未知量的界是否与实际 leakage 对齐；
2. 支撑边界。 cancellation-free 是否成立，unit-coefficient 支撑替身是否只用于 Algorithm 1，而没有误入有限求根；
3. 几何边界。 项序与 \(P\) 是否选得好，参数网格是否覆盖可能的优区间；
4. 格规约边界。 行列式条件只给充分条件，实际 LLL/Flatter 输出是否过 HG 阈值还依赖有限维常数；
5. 代数求根边界。 通过 HG 的多项式是否生成零维理想，variety 求解是否完整，候选是否经过原同余复验。

其中第 2 层和固定 \(P\) 后的第 3 层进入 Theorem 4 的证明；第 4、5 层属于端到端攻击；第 1 层在论文 API 之外。把失败统一叫 AssumptionError 虽然对调用者方便，却不足以做研究诊断，因此实现用 GeometryError、reduction log、ideal dimension 和 verified_roots 分别保留阶段信息。

Monic 也应单独看。若 leading coefficient 不是 1，三角格对角线上会多出系数因子，且除以 \(\operatorname{LM}(f_j)^{\ell_j}\) 时不能再把 leading term 当纯单项式处理。有时可以把多项式在模 \(M^{e_j}\) 下归一化，但这要求 leading coefficient 可逆；若它与模数有公因子，归一化本身可能泄漏 factor，也可能改变问题。论文把输入限定为 monic，避开了这条分支。

实现清单的未覆盖项

docs/2026-1027.md 文末带有一份 implementation checklist，但它是较早的快照。当前仓库后来加入了 test_paper_applications.py：CIHNP、MIHNP 3/4/5、ECHNP、LIPH 的精确指数，局部有理网格，以及 Appendix B Theorems 5–7 已经有断言。若直接引用旧 checklist，会错误地把这些项目继续列为 missing。

按当前测试目录重新核对，仍未覆盖的部分主要是：

• Table 2 的 15 组有限 LLL 根恢复实验没有完整参数化；
• Appendix A 的 parametric Presburger 与 eventual quasi-polynomial 证明没有可执行检查；
• \(P^\cup/P^\Sigma\) 的自动构造到参数搜索没有覆盖所有论文实例，部分测试直接手写目标 \(P\)；
• Appendix E.2 从密码关系到 MIHNP/ECHNP 多项式的恒等式没有独立符号校验；
• Algorithm 2 的多多项式、多模幂指数路径缺少与 Section 4 同等复杂度的端到端攻击测试。

测试文档发生漂移本身也是一条实现经验：论文转写、代码、测试和博客是四份会独立演化的材料。把 paper transcription 末尾的 checklist 当作实时真相并不安全。更稳妥的做法是由测试收集结果或 coverage manifest 自动生成映射，至少在新增测试时同步更新缺口列表。

Critical Reading. “有测试”与“论文 claim 被复现”之间还隔着输入忠实度。Section 4 的 unit-coefficient polynomials 精确复现 support-based Algorithm 1；若 claim 涉及原始系数、实际根或消元恒等式，则同一测试不够。证据应与 claim 使用的对象处在同一层。

小结

Coppersmith 的格构造、短向量与 Howgrave–Graham 判据保持不变。ePrint 2026/1027 处理的是渐近界的计算：

LP 最优值函数 \(\varphi_P\) 在有限个有理单元格上仿射，因此 \(\sigma_0=\int_P\varphi_P\) 与 \(\sigma_j=\int_Px_j\) 可以用精确有理算术求出。auto-copper 进一步检查 suitable set、行列式、HG 范数、零维理想与候选根的模关系。

该结论仍依赖 cancellation-free、Assumption 1，以及调用方给出的 \(P\) 与项序。实现从 equation (3) 起步，不包含密码系统到同余系统的 Gröbner 预处理；未覆盖实验列在上节的 implementation checklist 中。