科技学习系列 I ECM质因数分解 最后更新于 2025-05-01 22:45:34

https://www.luogu.com.cn/paste/j9wdc9z0 跑得很慢，但是把龟速乘换成蒙哥马利模乘应该能提升 $20$ 倍速度，~~但是不想写了~~省选后限时返场，写完了，两版代码分别支持(尚不清楚)和 $2^{119}$ 大小，$2^{115.5}$ 大小用时约 $\text{8.5s}$。新版代码支持 $2^{127}$，同样的数据跑了 $\text{0.1s}$，切换种子后有的跑了 $\text{0.2s}$ 或 $\text{0.5s}$。 ### 其他类似算法 考虑若找到 $a^2 \equiv b^2 \pmod n$ 则很有可能找到一个非平凡因子。 ```Pollard-rho:``` 考虑使用 $f(x)=x^2+c$ 的映射，使得在路线上走能够以 $O(t^2)$ 的速度检查近随机的 $(x,y)$ 对，复杂度 $O(\exp(\frac{1}{4}\ln n))$ ```Quatratic-sieve/CFRAC:``` 考虑随机一些 $x$ 使得 $x^2 \bmod n$ 是 ```B-powersmooth``` 的，也就是所有质因数都小于等于 $B$，然后做线性基即可找出线性相关组，得到 $(x_1x_2x_3)^2=y_1y_2y_3=z^2 \pmod n$。复杂度 $O(\exp((2+o(1))\sqrt{\ln n\ln\ln n}))$（不想分析，文献上是这么写的）考虑使用连分数近似计算 $\sqrt{kn}$，以使 $x^2 \bmod n$ 较小，更容易被 ```B-powersmooth``` 分解，复杂度 $O(\exp((\sqrt 2+o(1))\sqrt{\ln n\ln\ln n}))$，但是 [这篇文章](https://zhuanlan.zhihu.com/p/106650020) 说复杂度是 $O(\exp((1+o(1))\sqrt{\ln n\ln\ln n}))$，而且确实跑得很快。 ### 椭圆曲线理论科普 Q: $F_n$ 上的椭圆曲线半群是什么？ A: $E=\{(x,y) | y^2=x^3+ax+b ,x,y\in F_n \} \cup {O}$，$F_n$ 是模 $p$ 的有限域，$a,b$ 是椭圆曲线的参数，且 $4a^3+27b^2 \neq 0$，$O$ 是一个无穷远点。 Q: 椭圆曲线群上的加法是什么？ A: 考虑实数域几何意义，$P+Q=-R$，其中 $R$ 是连接 $P,Q$ 与曲线另一个的交点，特殊的若 $P=Q$ 则为切线；若 $P,Q$ 沿横轴对称则 $R=O$；否则若只有两个交点则 $P,Q$ 之一必为切点，取 $R$ 为那个切点。注意获取 $R$ 后需要沿横轴对称才能得到 $P+Q$ 的结果。此外，关于 $O$ 的加法满足 $O+P=P$。可以注意到这种加法是交换的，这种加法结合请读者自行证明，不想证了。 Q: 具体怎么做加法？ A: 考虑计算出共同直线的斜率，$P=Q$ 的情况下有 $s=\frac{y_P-y_Q}{x_P-x_Q}$，否则有 $s=\frac{3x^2+a}{2y}$，那么 $x_R=s^2-x_P-x_Q$，$y_R$ 可以根据 $x_R$ 计算。注意 $P+Q=-R$，而不是 $R$。此外，我们可以注意到 $P=Q$ 且 $y=0$时，或者 $P \neq Q$ 且 $x_P=x_Q$ 时几何意义上切线是竖直的，因此这种情况下加法得到无穷远点 $O$. $\bold{\text{Hasse's Theorem}}:$ 在 $F_p(p\in P)$ 上定义的椭圆曲线群 $E(Z/pZ)$，满足 $|E(Z/pZ)| \in [p+1-2\sqrt p,p+1+2\sqrt p]$ ### 算法简述(ECM 质因数分解) 考虑对曲线上的某个点计算 $(\prod\limits_{p\le B} p^{\lfloor \ln B/\ln p \rfloor})P$，考虑模 $n$ 的椭圆曲线半群，注意到若有 $n=pq$，且$(p,q)=1$，考虑中国剩余定理，那么这个半群的元素 $x$ 相当于两个半群的元素 $(x_p,x_q)$ ，其中 $x_p \in |E_p|,x_q \in |E_q|$。若 $|E_p|$ 是 ```B-powersmooth``` 的。而且 $E_q$ 不是或它们的最大质因数不同（这种概率是很大的，因为它们最大质因数相等是个很难达成的条件），则会得到 $(0,x_q)$，得到这样一个点的过程必然导致椭圆曲线加法的求逆步骤产生非 $0$ 的不可除因数，也就是 $p$ 。而若 $n=p^k$，同样可以运用上面步骤，但是我就不会证了。为啥对啊，我也不知道，有没有人评论一下指出。先咕着。 ### 参考文献 https://loj.ac/d/863 https://www.luogu.com.cn/blog/ycs-gg/Factorization-1 https://www.luogu.com.cn/paste/eha6wtkl https://www.cnblogs.com/tmzbot/p/9399023.html https://zhuanlan.zhihu.com/p/27159180 https://andrea.corbellini.name/ecc/interactive/modk-mul.html https://zhuanlan.zhihu.com/p/566394562