二次筛(Quadratic Sieve)

· · 个人记录

令欲分解的数为 n

考虑平方同余关系.

我们希望找到一组非平凡 (x{\neq}{\pm}y) 的 x^2\ {\equiv}\ y^2(mod\ n).

则 (x+y)(x-y)\ {\equiv}\ 0(mod\ n).

则 \gcd(x-y,n) 或者 gcd(x+y,n) 均为非平凡的因子.

为了找到这样的平方同余关系,dirc法是找到足量的 x 满足 z\ \equiv\ x^2(mod\ n) 是 B smooth的(最大质因子小于B).

这样的话可以把 z 分解到小于 B 的质数的指数基上(例如 基为2,3,5,7 : 63 = 3^2 * 7^1 : 0,2,0,1)

我们发现只要质数指数基相加后每一纬模 2 为 0 则必然为一平方数.

此时若我们找到足量的 z 就可以销出一组基是平方数.

有可能是平凡解,不过无妨,重新做即可.

所以我们只需要在模 2 意义下类似线性基的做就行.

二次筛的关键在于如何找到这样的 B smooth数.

对于一个固定的 B,x 越大,B smooth的几率就越小.

二次筛使用多项式来寻找适合的值,俱体来说考虑如下的多项式

f(x) = (x - \lfloor{\sqrt n}\rfloor)^2 - n

则对于 x 较小时 f(x) \approx 2x\sqrt{n} 这样 f(x) B smooth的几率就大大增加了.

我们考虑解这个方程 (x - \lfloor{\sqrt n}\rfloor)^2 \equiv n(mod\ p) 只需要求出二次剩余即可.

f(x) \equiv 0(mod\ p)$ 则 $f(x+p)\equiv 0(mod\ p)

这样,有一个 x 就会有很多 x 在 mod\ p 意义下同样为 0,可以直接拆出银子,这是一个类似于筛的过程,因此得名二次筛.

而我们又主意到,如果 n 在 mod\ p 意义下不是二次剩余,那么 f(x) \ mod\ p 不可能是 0.

所以只要取全部为二次剩余,解方程并得到可用部分然后筛出 B smooth 数最后消元即可得到一个不平凡的平方同余关系并大几率得到分解.

当然使用一个多项式一般是不够筛出足够的B smooth值的.

我们要使用多个多项式.

优化(们):

剩余一个大质数的可以合并(多个同样可以,不过比较复杂) 复杂度?: 筛到 $B$ 的话,期望大概有 $B/\ln(B)$ 个素数,其中是二次剩余的约有 $P = 0.5B/\ln(B)$ 个. 则进行高斯消元的复杂度就是 $P^3/w$ 级别的. 而筛分的几率设每轮筛到 $k$ ?. 则我们选取到的数大约是 $\sqrt{kn}$ 量级的. 则其剩余部分$B$ smooth的几率 $u=((\ln n + \ln k) / \ln B)*0.5

大约u^{-u} 的几率?

换言之筛分的复杂度就是 u^uP

则复杂度是?

不太懂,分析出来似乎就是 $e^{(1+o(1))\sqrt{\ln n\ln \ln n}}

实现了一下,分解 1e36 级别的数大约是 30ms.

代码:https://loj.ac/s/2030369