片段
Coppersmith
总结思路（逐步推理）和为什么 getFullP 里用多项式 P - N
为什么把多项式构造成 p(x) - n
一、从已知条件出发的代数关系（推导低位 p 的来源）
已知：RSA 参数 $n=pq$、公钥指数 $e=3$、私钥 $d$ 满足
$$ 3d \equiv 1 \pmod{\varphi(n)}. $$所以存在整数 $k$ 使得
$$ 3d = 1 + k\varphi(n). $$并且 $\varphi(n)=(p-1)(q-1)=n-p-q+1$。
两边乘以 $p$：
$$ 3pd = p + k\;p\varphi(n). $$把 $\varphi(n)$ 展开并化简（注意 $pq=n$）：
$$ p\varphi(n)=p(n-p-q+1)=p n - p^2 - p q + p = p n - p^2 - n + p. $$因此
$$ 3pd = p + k\big(p n - p^2 - n + p\big). $$现在你知道 $d$ 的低 512 位（代码里的 low_d = d & ((1<<512)-1)），于是把上式对 $2^{512}$ 取模：
这就是 phase4 里用 solve_mod(..., 2^512) 去解的同余方程——解出的就是 $p$ 的低 512 位候选（maybe_p）。
（代码里循环 $k=1$ 到 $3$ 是因为 $3d=1+k\varphi(n)$ 中 $k$ 通常很小，试几个小的 $k$ 就可以覆盖实际情形。）
二、从低位 $p$ 恢复完整的 $P$：为什么把多项式写成 $p(x)-n$
假设通过上一步我们得到了 $p$ 的低 512 位（记为 low_p）。把完整的素因子写成
其中 $x$ 是未知的高位整数量（待求）。令多项式（关于未知整数 $x$）
$$ p(x) := x\cdot 2^{512} + \text{low\_p}. $$关键事实：真正的 $x_0$（使得 $p(x_0)=P$）满足
$$ p(x_0) - n = P - n = -P(q-1). $$因此 $p(x_0)-n$ 被 $P$ 整除，换句话说
$$ p(x_0)-n \equiv 0 \pmod{P}. $$也就是说， $x_0$ 是多项式 $f(x)=p(x)-n$ 在模 $P$ 下的根（根是模 $P$ 的）。
Coppersmith 小根法（及其在 Sage/NTL 中的实现）可以 在已知合数 $n$ 的条件下 找到使得 $f(x)\equiv 0\pmod{p}$ 的“小”整数根 $x$（这里 $p$ 是 $n$ 的一个大素因子），前提是 $x$ 的绝对大小小于某个界（我们在代码中用 X=2^128 指定）。在 Sage 中通常把多项式放在 Zmod(n) 上，调用 .small_roots()，算法会寻找可以使得 $f(x)$ 在 $n$ 的某个素因子上为 0 的小根 —— 恰好是我们需要的 $x_0$。
因此把多项式构造成
$$ f(x) = p(x) - n $$的理由是：
- 对真实的 $x_0$，$f(x_0)=P-n$ 被 $P$ 整除：这给出了“模 $P$ 的零点”这一性质，正是 Coppersmith 能利用的结构。
- 我们知道 $n$ 和
low_p，所以 $f(x)$ 的系数是已知的整数（可直接构造）。 - 在实现上把多项式放在
PolynomialRing(Zmod(n))上并.monic().small_roots(X, beta)，可以在n上构造格并搜索在某个因子（即 $P$）模下的小根。
（补充：理论上用 $g(x)=p(x)$ 也是在模 $P$ 下为 0 的，但常见的做法是用 $p(x)-n$ 来把“与 $n$ 的整除关系”显式编码进多项式，这样在构造 lattice 时更自然，并且与已有实现习惯一致。）
三、参数选择与验证
p = x*2^512 + low_p：这是把已知低 512 位固定下来，未知高位写作 $x$。X = 2^128：这是对 $x$ 的上界估计。为什么 128？因为如果 $P$ 的总体位长是 $512+128=640$（例如），那么高位的范围就是 $<2^{128}$。你需要把X设为可以覆盖真实 $x$ 的值但又不能太大，否则 Coppersmith 的小根条件不会成立。beta = 0.4：这是小根算法的一个参数（表示目标模因子 $P$ 相对于 $n$ 的规模比），需要根据 $n$ 的长度与因子大小做合理设定。实务中会调整beta,X以保证算法能工作。.monic()：把多项式首项标准化为 1，便于用格方法做 LLL 等数值运算。- 找到候选根
r之后，getFullP返回p(r)，再验证P * (n//P) == n，这一步一定要做以排除错误根。
四、整体流程回顾
从
3d ≡ 1 (mod φ(n))、已知low_d通过模 $2^{512}$ 的方程求出 $p$ 的低 512 位候选maybe_p（phase4的前半部分）。对每个
low_p候选，调用getFullP(low_p, n)：- 构造 $p(x)=x\cdot2^{512}+{\rm low\_p}$；
- 构造 $f(x)=p(x)-n$（放在 $\mathbb Z_n[x]$）并用 Coppersmith（
.small_roots）找小根 $x$； - 若找到根，计算 $P=p(x)$，再
P*Q==n验证通过则成功恢复 $P,Q$。
恢复 $d=\text{inv\_mod}(3,\ (P-1)(Q-1))$，然后用 $m = c^d \bmod n$ 解密得到消息。
五、补充说明（直观理解）
- 把多项式写成
p(x)-n的直观原因：我们利用的是“$P$ 与 $n$ 的整除关系”。真实的 $x_0$ 使得 $p(x_0)$ 恰好等于 $P$，而 $P$ 是 $n$ 的因子，所以 $p(x_0)-n$ 在模 $P$ 下为 0——这就是 Coppersmith 能够抓住的模式。把已知的 $n$ 显式放进多项式，可以把“根模素因子”这一性质编码到求解问题里，从而用小根算法恢复未知高位。
关于整除的详解
1. 已知关系
我们已经知道：
$n = P \cdot Q$，其中 $P,Q$ 是素数。
$p(x)$ 的定义是：
$$ p(x) = x\cdot 2^{512} + \text{low\_p} $$真实的 $x_0$ 使得 $p(x_0)=P$。
2. 把 $p(x_0)-n$ 展开
代入 $p(x_0)=P$：
$$ p(x_0)-n = P - n $$再把 $n = P Q$ 代入：
$$ p(x_0)-n = P - P Q = P(1 - Q) = -P(Q-1) $$3. 得出整除结论
右边是 $-P(Q-1)$，显然含有因子 $P$，所以：
$$ p(x_0)-n \equiv 0 \pmod{P} $$换句话说，对模 $P$ 来说，$x_0$ 是多项式 $p(x)-n$ 的一个根。
4. 为什么重要
我们并不知道 $P$，但是我们知道 $n$。把多项式放在模 $n$ 的多项式环里，去找一个小的整数根 $x$，Coppersmith 方法就能找到这个 $x_0$，因为它必须满足：
- 在模 $P$ 下 $p(x_0)-n=0$，而且
- $x_0$ 是一个很小的整数
一旦找到了 $x_0$，就能恢复 $P = p(x_0)$。