部分质因数分解法学习笔记

检查所有 $\le \sqrt n$ 的因数，复杂度为 $O(\sqrt n)$。

我们注意到对于值域为 $[0,n-1]$ 的随机序列 $a$，$\min \{ i \mid \exists j > i, a_i = a_j \}=O(\sqrt n)$，这时可以用 $\gcd(a_i-a_j,n)$ 提取出 $n$ 的因子，且大概率是非平凡的。

随机取一个 $c$ ，我们认为 $a_{k+1}=(a_k^2+c) \bmod n$ 是随机的，因此这一过程期望进行 $O(\sqrt p)$ 次，时间复杂度 $O(\sqrt p \log n)$ ，可以通过实现去掉 $\log$ 。

以下的部分在 OI 中几乎没有用。

我们注意到，如果 $a^2 \equiv b^2 \pmod n$，那么 $(a+b)(a-b) =kn$，因此如果 $n \nmid a-b$ 且 $n \nmid a+b$ 则可以提取因数。

由于这一过程对 $a,b$ 本身没有要求，因此可以将一些预先选出的 $a_i,b_i$ 乘起来。设选出了 $k$ 个 $(a_i,b_i)$ 对，我们让 $a_i$ 为平方数，这样就只需要考虑 $b_i$ 。令 $p_i$ 为全体素数，$b_i=p_1^{e_1}p_2^{e_2} \dots$，只需要关注 $e_i \bmod 2$ 的值。

设 $B$ 为 $b_i$ 因数中素数编号的最大值，则问题实际上等价于，每个 $i$ 对应 $0/1$ 向量 $v_i =[e_1,e_2 \dots e_B]$，要选出集合 $S$ 使 $\sum \limits_{i\in S} v_i \equiv 0 \pmod 2$ 。由线性代数知识，我们可以知道至少有 $2^{k-r}-1$ 个解，其中 $r$ 为 $[v_1 \dots v_k]^T$，有 $r \le B$，因此取 $k=B+O(1)$ 即可以极大概率得到非平凡的解，使用高斯消元即可。

接下来的问题是，对于 $B$ 如何快速生成较多的 $(a_i,b_i)$ 对，且 $b_i$ 没有大于 $p_B$ 的因数。令 $m=\lceil \sqrt n\rceil$，设 $(a'_i,b'_i)=(i,(m+i)^2-n)$，此时 $b'_i=O(i\sqrt n)$，因此可以用这个公式找到较多的 $(a'_i,b'_i)$ 。

我们发现，对于 $p \mid n$ 有 $b'_{i+kp} \equiv (i+kp+m)^2-n \equiv (i+m)^2+2kp(i+m)-n\equiv b'_i \pmod p$，因此对满足 $n$ 在模 $p$ 下有二次剩余的 $p$，可以批量处理 $(a'_i,b'_i)$。对于 $0 \le i<p$，若 $(i+m)^2 -n\equiv 0 \pmod p$ 则有 $i \equiv \pm \sqrt n -m \pmod p$，需要用 Cipolla 算法求出二次剩余。

对这些 $i$ ，我们有 $b'_{i+kp}$ 均为 $p$ 的倍数。对于所有 $j \le B$，枚举 $p_j$ ，计算二次剩余，将所有满足条件的 $b'_i$ 除以 $p_j$ ，最后剩余 $b'_i=1$ 的 $i$ 即满足没有大于 $p_B$ 的因数。可以证明，这样得到的 $i$ 个数远大于 B。

复杂度是 $L_n[\dfrac{1}{2},1]=e^{(1+o(1))\sqrt{\ln n \ln \ln n}}$ 的，实际上 $10^{18}$ 以内跑的比 Pollard-rho 慢，$10^{30}$ 大概需要 $0.5$ 秒。

我们注意到，若 $p \mid n$ 则有 $x^{p-1} \equiv 1 \pmod p$ 对 $p \nmid x$ 成立，因此我们可以用 $\gcd(x^{p-1}-1,n)$ 提取 $p$ 。但是我们不知道 $p$，所以我们取一个 $B$，令 $k=\prod \limits_{q \le B}q^{\lfloor \log_q B \rfloor}$，则若 $p-1$ 的所有素因子都 $\le B$ ，一定有 $p-1 \mid k$。

这样我们就可以使用 $\gcd(x^k,n)$ 得到 $p$。对于一个特定的 $B$ ，这样做的复杂度为 $O(B\log B \log^2 n)$，在 $p-1$ 较为光滑（质因子较小）时很有效。

一个例外是，对于一个 $B$，如果 $n$ 的所有素因子 $p_i$ 都满足 $p_i-1$ 的所有素因子 $\le B$，此时 $\gcd(x^k,n)=n$ ，我们无法提取因数。

我们定义一个以 $P(n)$ 概率成功，复杂度为 $T(n)$ 的算法的期望复杂度为 $\dfrac{T(n)}{P(n)}$，可以证明对于 $B=\sqrt{n}^{\frac{1}{a}}$，有 $P(n)=a^{-a}$。因此这一算法的（期望）复杂度也为 $e^{(1+o(1))\sqrt{\ln n \ln \ln n}}$ 。这同时给出了这一类方法的复杂度下限。

考虑形如 $C:y^2=x^3+ax+b$ 的曲线，其中 $4a^3+27b^2 \neq 0$。

椭圆曲线群是定义在 $C$ 上的群，运算 $P + Q$ 为点 $P$ 和点 $Q$ 的连线与 $C$ 的交点的对称点。一条直线与 $C$ 只能有 $1$ 或 $3$ 个交点（记重数），而我们已经确定 $2$ 个，因此 $P+Q$ 存在且唯一。特别的，若 $P=Q$，我们定义连线为 $C$ 过 $P$ 的切线。

定义群中的 $0$ 为无穷远点。我们让 $P+0=P$ 恒成立，同时我们定义形如 $P(x,y),Q(x,-y)$ 的直线交 $C$ 于无穷远点。

实际计算中在模 $p$ 意义下进行，这并不会改变定义。此时的 $0$ 在分母为 $p$ 的倍数时出现。

我们发现 Pollard p-1 算法的效率依赖于 $(\Z/p\Z)^*$ 的结构，如果 $p-1$ 包含较大的因子就会失效。考虑使用椭圆曲线群进行这一操作，由 Hasse 定理我们有 $p + 1 - 2\sqrt{p} \le n_p \le p + 1 + 2\sqrt{p}$ 成立，因此通过随机选取参数 $a,b$ 有较多的群可供选取。

选定 $B$ 之后，我们随机 $P_0$，在椭圆曲线群中计算 $P=P_0\prod \limits_{q \le B}q^{\lfloor \log_q B \rfloor}$，数乘定义为多次进行加法。过程中如果出现 $0$ 那么相当于寻找到了因子，我们再通过 $\gcd$ 提取即可。

一条曲线可能不足以完成分解，我们随机生成多条曲线即可。算法在椭圆曲线的阶因子均不超过 $B$ 时完成，复杂度为 $e^{(\sqrt2+o(1))\sqrt{\ln p \ln \ln p}}$ ，渐进意义下不劣于二次筛法，并且在因子较小时效率更高。然而因为椭圆曲线群需要维护大量模意义下的运算，一般情况下跑不过二次筛法。/youl

🫷够了