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

· · 算法·理论

1.指数复杂度做法

1.1 暴力分解

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

1.2 Pollard Rho

我们注意到对于值域为 [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 。

实现

2.亚指数复杂度做法

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

2.1 二次筛法

我们注意到，如果 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 秒。

实现

2.2 椭圆曲线分解法

2.2.1 Pollard p-1 算法

我们注意到，若 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}} 。这同时给出了这一类方法的复杂度下限。

2.2.2 椭圆曲线群

考虑形如 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 的倍数时出现。

2.2.3 椭圆曲线分解法

我们发现 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

3.科技

3.1 通用数域筛法

🫷够了