本文面向会做乘除法、理解平方，但不熟悉同余、光滑数和线性代数的读者。前八步解释“为什么能用光滑数拼出因数”，后面再介绍筛法、GNFS 和 GPU 如何提高效率。

我们要解决的问题是：给定一个合数 \(N\)，找到两个大于 1 的整数，使它们的乘积等于 \(N\)。RSA 中通常有 \(N=pq\)，其中 \(p,q\) 是两个不同的大质数。真正需要分解的是合数 \(N\)。

整条推导可以先记成：

收集“平方与某个数同余”的关系 → 挑选一些关系，使右侧乘积成为平方 → 得到平方同余 → 用最大公约数提取因数。

第一步：同余只表示“除以同一个数，余数相同”

例如：

\[100=1\times91+9,\qquad 9=0\times91+9.\]

100 和 9 除以 91，余数都是 9。这件事写成：

\[100\equiv9\pmod{91}.\]

这里 \(\equiv\) 读作“同余”，\(\pmod{91}\) 表示“以 91 为模”。它不表示 \(100=9\)。

如果两个数余数相同，把它们相减，余数部分就抵消了，剩下的是 91 的整数倍：

\[100-9=91.\]

一般地：

\[A\equiv B\pmod N \quad\Longleftrightarrow\quad N\text{ 整除 }A-B.\]

“整除”就是除完没有余数。例如 7 整除 91，但 10 不整除 91。

这一步得到的工具：两个数同余，就能把它们的差写成 \(N\) 的倍数。

第二步：为什么两个平方同余，就可能暴露因数？

假设找到了 \(x,y\)，满足：

\[x^2\equiv y^2\pmod N.\]

根据第一步，\(x^2-y^2\) 是 \(N\) 的倍数。再利用平方差公式：

\[x^2-y^2=(x-y)(x+y).\]

于是我们知道：

\[N\mid(x-y)(x+y).\]

符号 \(\mid\) 表示“整除”。这句话的意思是：\(N\) 能整除整个乘积。

当 \(N=pq\)，且 \(p,q\) 是不同质数时，有用的情况是：\(p\) 出现在其中一项里，\(q\) 出现在另一项里。计算某一项与 \(N\) 的最大公约数，就能把它们共有的因子取出来。

最大公约数写作 \(\gcd\)。例如 \(\gcd(14,91)=7\)，因为 14 和 91 共有的最大正因数是 7。

现在分解 \(N=91\)。已知：

\[10^2\equiv3^2\pmod{91}.\]

所以：

\[(10-3)(10+3)=7\times13=91.\]

分别求最大公约数：

\[\gcd(10-3,91)=7,\qquad \gcd(10+3,91)=13.\]

因此 \(91=7\times13\)。

一般情况下，\(x-y\) 和 \(x+y\) 不一定恰好就是两个因数，所以需要求 GCD。例如 \(20^2\equiv13^2\pmod{77}\)，得到的是：

\[(20-13)(20+13)=7\times33=3\times77.\]

其中 33 还夹带一个多余的因子 3，而 \(\gcd(33,77)=11\) 能取出我们需要的部分。

为什么还要检查“非平凡”？

如果 \(x\equiv y\pmod N\)，则 \(x-y\) 本身就是 \(N\) 的倍数，得到 \(\gcd(x-y,N)=N\)，没有提供新信息。

如果 \(x\equiv-y\pmod N\)，则 \(x+y\) 是 \(N\) 的倍数，同样可能没有用。

因此，一个足以保证成功的条件是：

\[x\not\equiv y\pmod N, \qquad x\not\equiv-y\pmod N.\]

在平方同余成立的前提下，这两个条件保证：

\[1<\gcd(x-y,N)<N.\]

理由是：这个 GCD 不可能等于 \(N\)，否则 \(N\) 整除 \(x-y\)；也不可能等于 1，否则 \(x-y\) 与 \(N\) 互质，从 \(N\mid(x-y)(x+y)\) 就能推出 \(N\mid x+y\)。两种情况都与条件矛盾。

实际计算时，直接求出 \(d=\gcd(x-y,N)\)，检查 \(1<d<N\) 即可；成功后，另一个因子就是 \(N/d\)。

现在的问题变成：不知道因数时，怎样找到有用的平方同余？

第三步：为什么计算中可以先取余数？

先解释后面会反复使用的规则：把一个数替换成它除以 \(N\) 的余数，不会改变加法、乘法和平方运算的最终余数。

例如：

\[260=3\times77+29.\]

把它平方展开：

\[260^2=(3\times77)^2+2\times3\times77\times29+29^2.\]

前两项都是 77 的倍数，取余数后没有贡献，所以：

\[260^2\equiv29^2\pmod{77}.\]

这不表示两个平方相等，而是表示它们除以 77 的余数相同。

因此，如果我们已经知道 \(260^2\equiv15^2\pmod{77}\)，就可以写成：

\[29^2\equiv15^2\pmod{77}.\]

直接验证：

\[29^2=841=10\times77+71,\] \[15^2=225=2\times77+71.\]

取余数还保留后续的 GCD：因为 \(260-15=(29-15)+3\times77\)，所以：

\[\gcd(260-15,77)=\gcd(29-15,77).\]

保留 260 计算也可以。提前取余数，是为了避免中间数字随着不断相乘而变得过大。

另外，同余关系可以相乘。如果 \(A\equiv a\pmod N\)、\(B\equiv b\pmod N\)，写成 \(A=sN+a\)、\(B=tN+b\)，展开后有：

\[AB=stN^2+sbN+taN+ab\equiv ab\pmod N.\]

这一步得到的工具：可以把若干条同余关系相乘，并随时对中间结果取余数。

第四步：相同余数很有用，但我们不必只等相同余数

假设找到：

\[X^2\equiv K\pmod N,\qquad Y^2\equiv K\pmod N.\]

那么有两种处理方式。

第一种，直接得到 \(X^2\equiv Y^2\pmod N\)，尝试 \(\gcd(X-Y,N)\)。

第二种，把两条关系相乘，得到：

\[(XY)^2\equiv K^2\pmod N,\]

再尝试 \(\gcd(XY-K,N)\)。

两种构造都成立，但各自都要检查是否得到非平凡因数；第一种已经可以尝试分解，不必先相乘。

例如前面的 \(13^2\equiv15\pmod{77}\) 和 \(20^2\equiv15\pmod{77}\)，直接相减就够了。

不过，相同余数只是一个特殊机会。相乘真正拓宽了可用的关系：右侧的数可以各不相同，只要选出来的乘积是平方。

下面用一个需要组合不同余数的例子说明。

第五步：完整例子——把不同余数拼成平方，分解 143

我们要分解 \(N=143\)，找到两条关系：

\[17^2=289=2\times143+3,\] \[19^2=361=2\times143+75.\]

也就是：

\[17^2\equiv3\pmod{143},\qquad 19^2\equiv75\pmod{143}.\]

3 和 75 不相同，所以不能直接认为 \(17^2\) 与 \(19^2\) 同余。

但右侧相乘有一个好性质：

\[3\times75=225=15^2.\]

于是，按照第三步的相乘规则：

\[17^2\times19^2\equiv3\times75\pmod{143}.\]

左侧本来就是两个平方的乘积，天然可以合成一个平方：

\[(17\times19)^2\equiv15^2\pmod{143}.\]

把左边的底数取余数：

\[17\times19=323=2\times143+37.\]

因此：

\[37^2\equiv15^2\pmod{143}.\]

最后求 GCD：

\[\gcd(37-15,143)=\gcd(22,143)=11.\]

若不知道怎样求 GCD，可以用辗转相除法：

\[143=6\times22+11,\qquad22=2\times11.\]

最后一个非零余数是 11，所以最大公约数为 11。另一个因子为 \(143/11=13\)。

至此，我们只用了两条余数不同的关系，就得到了 \(143=11\times13\)。

环节 具体结果 为什么能继续
收集关系 \(17^2\equiv3\)，\(19^2\equiv75\)，模数均为 143 左侧已经是平方
组合右侧 \(3\times75=15^2\) 右侧乘积也成为平方
合并并取余 \(37^2\equiv15^2\pmod{143}\) 323 可以替换成余数 37
提取因数 \(\gcd(37-15,143)=11\) 平方差中包含 143 的因子

接下来的难点：有很多不同的右侧数时，怎样系统地找到乘积为平方的组合？

第六步：为什么“每种质因子的数量都是偶数”就能拼成平方？

先暂时离开取余数，单独看普通整数相乘。

\[12=2\times2\times3,\qquad 18=2\times3\times3,\qquad 6=2\times3.\]

三个数全部相乘，里面一共有四个 2、四个 3。每一种都能平均分成两份：

\[12\times18\times6 =(2\times2\times3\times3)(2\times2\times3\times3) =36^2.\]

指数只是记录“同一种质因子出现了几次”。用指数写，就是：

\[12\times18\times6 =2^{2+1+1}\times3^{1+2+1} =2^4\times3^4 =(2^2\times3^2)^2.\]

所以，对一个正整数来说：

每种质因子的指数都是偶数，等价于整个数是一个整数的平方。

平方根的计算方法也随之确定：把每个指数除以 2，再相乘。

这里的 12、18、6 只用来解释配对规则，没有假设它们恰好是某个指定 \(N\) 下三个平方的余数。完整分解仍使用第五步已经验证过的 143 例子。

第七步：光滑数的作用，是把要配对的质因子限制在一张固定清单内

指定一个界限 \(L\)。如果一个正整数的所有质因子都不超过 \(L\)，就称它为 \(L\)-光滑数。

例如取 \(L=5\)，允许的质因子只有 \(2,3,5\)：

数字 质因数分解 是否为 5-光滑数
12 \(2^2\times3\) 是
18 \(2\times3^2\) 是
75 \(3\times5^2\) 是
3600 \(2^4\times3^2\times5^2\) 是
14 \(2\times7\) 否，含有 7

“光滑”描述的是质因子的大小。一个数本身可以很大，但只要由这几个小质数相乘而成，仍然是光滑数。

为什么要限制质因子？因为我们想找的是“每一种质因子都能凑成偶数”的组合。所有候选都使用同一张有限清单，才方便把问题统一表示出来。

比如，候选都只使用 \(2,3,5\)，我们始终只需要检查这三种质因子的数量。若某个候选含有一次 101，而其他候选都不含 101，选上它就会留下一个无法配对的 101。

光滑数带来两个直接好处：

  1. 可以用已知的小质数做试除，得到明确的分解记录。
  2. 可以把所有候选放在相同的坐标下，系统地寻找指数配对的组合。

“光滑”不等于“已经是平方”。例如 12 是 5-光滑数，却不是平方；它的作用是参与组合。

也不保证任意几个光滑数相乘都会成为平方。例如 \(12\times18=216=2^3\times3^3\)，指数仍然是奇数。还需要选出合适的组合。

第五步的 3 和 75 都是 5-光滑数；它们恰好可以组合成平方。这就是光滑数如何进入实际分解过程。

第八步：只记奇偶性，就把“选哪些数”变成了线性代数

判断能否配对时，暂时不必知道指数究竟是 2、4 还是 6，只需要知道它是偶数。用 0 表示偶数，1 表示奇数。

以质因子清单 \(2,3,5\) 为列：

数字 2 的指数奇偶 3 的指数奇偶 5 的指数奇偶
12 0 1 0
18 1 0 0
6 1 1 0

相乘时，指数相加。对应的奇偶规则是：

\[0+0=0,\quad0+1=1,\quad1+0=1,\quad1+1=0\qquad\text{（模 2）}.\]

最后一条表示“奇数加奇数得到偶数”。它也正是计算机里的 XOR（异或）规则。

因此，三个向量组合后：

\[(0,1,0)\oplus(1,0,0)\oplus(1,1,0)=(0,0,0).\]

全零表示所有质因子的数量都是偶数，乘积就是平方。

数量多了以后，可以把每条关系的奇偶向量放成矩阵的一列。用向量 \(v\) 表示选择：某一项为 1 就选该关系，为 0 就不选。目标是求：

\[Mv=0\qquad\text{（所有运算都按模 2 进行）},\]

并且 \(v\) 不能全为零，因为“一个都不选”没有意义。这就是在线性代数中寻找非零的零空间向量。

如果有 \(k\) 个质因子，也就是 \(k\) 个奇偶约束，那么收集超过 \(k\) 条这样的正整数关系后，一定存在非空组合，使这些指数全部为偶数。不过，得到的平方同余仍可能是平凡的，需要尝试其他组合。

计算机因此不必枚举所有关系子集。小例子可以使用模 2 高斯消元；大规模任务使用适合稀疏矩阵的算法。

最后要真正开平方时，还需要原始的完整指数。“只记奇偶性”用于寻找组合，不能丢掉重建平方根所需的原始关系。

第九步：把前八步连成一个可执行的分解流程

先看一个教学流程。选择质因子界限 \(L\)，然后：

  1. 尝试不同的整数 \(a_i\)，计算 \(r_i=a_i^2\bmod N\)。如果先发现 \(1<\gcd(a_i,N)<N\)，已经分解成功。
  2. 当 \(r_i>0\) 时，尝试用不超过 \(L\) 的小质数将它完全分解；成功则保留关系 \(a_i^2\equiv r_i\pmod N\) 及其分解。
  3. 收集足够多的关系后，用指数奇偶性找出一个非空子集 \(S\)，让右侧乘积成为平方：
\[\prod_{i\in S}r_i=Y^2.\]
  1. 把对应的左侧底数相乘，并取余数：
\[X=\left(\prod_{i\in S}a_i\right)\bmod N.\]
  1. 因为同余可以相乘，所以 \(X^2\equiv Y^2\pmod N\)。计算 \(d=\gcd(X-Y,N)\)。
  2. 如果 \(1<d<N\)，返回 \(d\) 和 \(N/d\)；否则尝试另一组关系，必要时继续收集。

这个按平方余数收集关系的流程接近 Dixon 方法的基本框架，说明了筛类分解算法共用的组合思想；它本身还不是完整的二次筛或 GNFS。

为什么收集到的关系不必全部使用？

以 \(N=77\) 为例，有：

\[9^2\equiv4,\quad13^2\equiv15,\quad20^2\equiv15\pmod{77}.\]

三条全选，右侧乘积是 \(4\times15\times15=30^2\)，左侧底数取余数也是：

\[9\times13\times20\equiv30\pmod{77}.\]

结果只是 \(30^2\equiv30^2\pmod{77}\)。这次组合给出 \(\gcd(0,77)=77\)，没有完成分解。

只选后两条，得到的是 \(29^2\equiv15^2\pmod{77}\)，求 GCD 就能得到 7。

因此，收集关系、选择组合、验证是否成功，是三个不同环节。

第十步：“筛法”如何让关系收集更快？

前面的教学流程逐个计算余数、逐个试除。它容易理解，但对大数还不够高效。

二次筛使用：

\[Q(a)=a^2-N, \qquad a^2\equiv Q(a)\pmod N.\]

这里 \(Q(a)\) 是与 \(a^2\) 同余的整数，不必是 \(0\) 到 \(N-1\) 之间的标准余数。选择靠近 \(\sqrt N\) 的 \(a\)，通常可以让 \(\lvert Q(a)\rvert\) 相对较小；较小的数更容易完全由小质因子构成。

“筛”进一步利用了整除位置的规律。对一个小质数 \(\ell\)，先求出满足：

\[a^2\equiv N\pmod\ell\]

的余数类。每个这样的余数类都告诉我们：哪些位置的 \(Q(a)\) 一定能被 \(\ell\) 整除。沿着等差数列批量处理这些位置，比每个位置重新尝试所有质数便宜。

实际实现常累计小因子的对数分数，先筛出可能光滑的候选，再精确试除确认。分数只是筛选依据，最终仍要验证整数分解。

如果 \(Q(a)\) 为负，还要把符号作为一个额外的奇偶约束：选出的负数个数必须为偶数，乘积才能为正平方。前面的正数例子暂时避开了这一细节。

光滑界限也需要权衡：界限太小，关系很难找到；界限更大，关系可能更容易找到，但质因子清单和后续矩阵也会变大。

第十一步：GNFS 为什么引入“数域”？

到这里已经知道，我们真正需要的是一组关系：组合之后，可以构造两个平方同余。

GNFS（通用数域筛法）换了一种构造关系的方式，同时在普通整数和一个数域中寻找可组合的对象。通过合适的多项式，可以让需要满足光滑性的整数表达式更有利。

下面只说明连接两侧的数学桥梁，省略实际实现中的系数、分母与平方根修正。

先让两个世界遵守相同的多项式规则

选择一个多项式 \(f(t)\) 和整数 \(m\)，满足：

\[f(m)\equiv0\pmod N.\]

再引入一个代数数 \(\alpha\)，满足 \(f(\alpha)=0\)。这类似于通过 \(i^2+1=0\) 引入虚数 \(i\)，只是多项式可以更复杂。

因为 \(m\) 在模 \(N\) 意义下也满足这个规则，可以建立一个保持加法、乘法的映射：将有关表达式中的 \(\alpha\) 替换为 \(m\)，然后对 \(N\) 取模。

对每一对整数 \((a,b)\)，同时考虑：

一侧 对象
普通整数侧 \(a-bm\)
数域侧 \(a-b\alpha\)

在筛选数域侧时，会使用“范数”这个整数表达式来判断是否适合分解，并记录与素理想有关的分解信息。可以先把范数理解为连接代数对象和整数筛选的工具。

再让同一批关系在两侧都成为平方

目标是选出同一批 \((a_i,b_i)\)，使：

\[\prod_i(a_i-b_i m)=X^2, \qquad \prod_i(a_i-b_i\alpha)=\beta^2.\]

把第二个等式通过上述映射送回模 \(N\) 的整数中。如果 \(\beta\) 映射为 \(Y\)，就得到：

\[Y^2\equiv\prod_i(a_i-b_i m)=X^2\pmod N.\]

这又回到了第二步的目标，可以尝试 \(\gcd(X-Y,N)\)。

这里两侧必须选择同一批关系，否则映射之后的乘积对不上。

GNFS 的完整数学比普通整数的指数配对更复杂：代数侧需要素理想分解和额外的平方性约束。范数为平方，不足以推出代数对象本身是平方。 前面的整数奇偶表解释了组合思想，但不能直接替代整个代数侧。

第十二步：GPU 加速的是这条流程中的哪些工作？

理解前面的步骤后，可以把硬件任务对应起来：

计算阶段 数学上在做什么 并行特点
多项式选择 找到能产生较多光滑关系的表达式 不同候选可以并行评估
筛选与关系收集 找到两侧适合分解的 \((a,b)\) 不同搜索区域可分发到大量计算设备
余因子分解 继续分解除去小因子后的剩余部分 许多独立的小任务，但耗时不一致
过滤 去重、合并与删减关系，缩小矩阵 不规则数据处理和内存访问较多
稀疏线性代数 找到使指数奇偶相消的关系组合 需要处理共同的大矩阵，带宽和通信很关键
平方根与 GCD 构造最终平方同余并提取因数 GCD 通常很便宜；代数平方根仍有专门算法

GNFS 常用 special-q 格筛：先固定代数侧的一个已知质因子条件，搜索满足条件的整数对。不同 special-q 可以形成大量相对独立的关系收集任务。

GPU 上的核心工程问题，是如何高效处理这些任务。筛选的写入位置较零散，需要分桶和局部处理；小质数命中频繁、大质数命中稀疏，需要按工作量分配线程；余因子分解也需要避免少数困难任务拖住整批计算。

矩阵阶段则对应第八步的模 2 运算，常用 Block Wiedemann 或 Block Lanczos 等方法。它大量使用位运算和稀疏访存，不能把 AI 训练的浮点矩阵乘法峰值直接换算为分解性能。

因此，评估 GPU 实现应看每秒产出多少有效关系、矩阵求解需要多久，以及完整任务的计算成本。某个筛选内核提速，并不表示整个分解任务按同样倍数提速。

阅读 RSA 分解新闻时，需要区分的三件事

RSA-260 指一个有 260 位十进制数位、862 位二进制位的特定挑战数。RSA-2048 通常表示 2048 位二进制的 RSA 模数，两种数字口径不同。

公开一个因数，可以通过整除快速验证；它本身不能说明发现因数时用了什么算法、多少 GPU 或多长时间。算法、硬件规模和耗时，需要计算报告提供。

GNFS 改善的是构造和收集关系的方法；GPU 实现改善的是实际执行效率。某个较短模数被分解，不能据此把更长模数的成本按位数比例外推。

来源与进一步阅读

数学推导和数值例子可直接按文中步骤复算。进一步了解完整算法，可以参考以下资料。