破解互联网密码的人类最强数学“一般数域筛选法（GNFS）”是什么？

我们每天使用的互联网，无论是LINE消息、YouTube还是在Amazon上购物，所有的通信都受到“密码”的保护。目前，全世界使用最广泛的密码代表就是“RSA密码”。

RSA密码防御的核心非常简单。那就是利用了 “即使是计算机也无法解开巨大数字的质因数分解” 这一数学性质。例如，如果是“15”，我们很快就能知道是“3 × 5”，但如果这变成一个“270位的数字”，即使把全世界的超级计算机联合起来，也需要几亿年才能解开。

然而，数学家们也没有沉默。为了打破这个坚不可摧的密码，人类创造出了一种如同魔法般的算法（计算步骤）——“一般数域筛选法（GNFS：General Number Field Sieve）”。

在这篇文章中，我们将不使用任何专业术语，仅凭 初中学的数学知识（质因数分解、代数式、最大公约数），分步为您完全解析这个“人类最强算法”破解密码的奥秘！

第1章：密码破译的目标是“初三的公式”

面对巨大的质因数分解，最大的必杀技就是初三年级学的这个公式。

$X^2 - Y^2 = (X + Y)(X - Y)$

你可能会想：“哎，这么基础的公式就能破解密码吗？”但正是这个公式，是解开一切的大师级钥匙。

破解密码的最大目标，是对于一个巨大的数字 $N$，找到 “将 $X^2$ 和 $Y^2$ 除以 $N$ 后的余数相同的数字（$X$ 和 $Y$）”。

为什么“余数相同”就能解开密码？

假设有两个数字 $X^2$ 和 $Y^2$，“除以 $N$ 的余数相同”。余数相同意味着，做减法得到的“$X^2 - Y^2$”，必定能被 $N$ 整除（成为 $N$ 的倍数），这是一个法则。

这里，假设用于密码的巨大数字 $N$ 是由两个秘密的质数（$p$ 和 $q$）相乘得到的（$N = p \times q$）。

将 $X^2 - Y^2$ 进行因式分解，就变成了 $(X - Y)(X + Y)$。这既然是 $N$ 的倍数，就意味着在这个乘法中的某个地方，隐藏着秘密的质数 $p$ 和 $q$。

奇迹在此发生。这两个质数 $p$ 和 $q$，“$p$ 进入 $(X - Y)$ 的房间”、“$q$ 进入 $(X + Y)$ 的房间”，被分到不同房间的概率，在数学上是 ** 50%（二分之一）**。

在只有质数 $p$ 进入了 $(X - Y)$ 房间的状态下，让我们来计算 $(X - Y)$ 和 $N$ 的 “最大公约数（最大的共同部分）”。

$(X - Y)$ 的内容＝ $p \times$ 某个数
$N$ 的内容＝ $p \times q$ 共同的部分只有 “$p$” 吧！

也就是说，在计算出最大公约数的瞬间，隐藏着的质数 $p$ 就会掉落出来，密码也就被完全破译了。（※使用“辗转相除法”，即使在智能手机上也能瞬间计算出最大公约数）

【小专栏：为什么是平方？三次方或两倍不行吗？】

如果是“$2X - 2Y$”，就会变成 $2(X - Y)$，因为只有一个房间，所以无法分离出质数。如果是“$X^3 - Y^3$”，房间的大小会变得不平衡，计算量会无谓地增加。为了将质数分离成两个，能优美地分成两个房间的“平方”性价比最高。

第2章：如何寻找X和Y？“收集质数卡片的拼图”

目标已经明确。然而，即使盲目地去寻找“余数相同的 $X^2$ 和 $Y^2$”，直到宇宙寿命结束也找不到。于是，数学家们想出了一个极其天才的方法，称为 “收集质数卡片的拼图”。

Step 1：用筛子只收集沙金（平滑数）

首先，准备一个随意的数字 $Z$，计算其平方后除以 $N$ 的余数 $W$。（$Z^2 = W$ 的余数世界）

将得到的余数 $W$ 进行质因数分解。这里，只有当出现 “仅由 2, 3, 5, 7 等小质数组成的 $W$” 时，才将该式子作为“中奖卡片”保留下来；如果混杂了大的质数就丢掉。这就好比在河里用筛子把大石头过滤掉，只收集沙金一样的作业。

Step 2：全部变成“偶数个”的拼图

例如，假设收集到了以下 3 张沙金卡片：

卡片A： $Z_1^2 = 2^3 \times 3^1$
卡片B： $Z_2^2 = 2^1 \times 5^1$
卡片C： $Z_3^2 = 3^1 \times 5^1$

我们把它们全部相乘看看。右侧变成 $(2^3 \times 3^1) \times (2^1 \times 5^1) \times (3^1 \times 5^1)$，整理后变成 “$2^4 \times 3^2 \times 5^2$”。

不可思议的是，质数的个数变成了“4个、2个、2个”，全部都是偶数个！全部都是偶数个，意味着把整体的个数减半，就会变成“某个数的平方”。也就是说，$(2^2 \times 3^1 \times 5^1)^2 = (60)^2$。

左侧是 $(Z_1 \times Z_2 \times Z_3)^2$，这样一来，终于 $X = (Z_1 \times Z_2 \times Z_3)$ $Y = 60$ 这组期待已久的“$X^2 = Y^2$”就完成了！

对于计算机来说，计算质数个数是“偶数还是奇数（0还是1）”的拼图是它非常擅长的，所以用这种方法能高速地找到 $X$ 和 $Y$。

第3章：阻挡在前的绝望之墙

这样就能解开任何密码了！……正当这么想时，大问题发生了。如果密码数字 $N$ 在“100位”左右，用这个方法（称为二次筛选法）还能解开；但如果 $N$ 变成“200位、300位”，计算途中出现的 $W$ 就会变得太大。

数字太大的话，“仅由小质数组成的数（沙金）”就会彻底不再出现。这会变得比在沙漠里找隐形眼镜还难，完全收集不到用来解开拼图的卡片。

在这里，人类的终极武器 “一般数域筛选法（GNFS）” 终于登场了。

第4章：人类最强的点子，创造“两个世界”

GNFS 的天才构想是：“因为只在现实世界里计算，所以数字才会变大。那么，就创造一个使用多项式（代数式）的『里世界』，把计算的负担分散成两份吧。”

代数式的魔法

GNFS 利用一个基准数 $m$，将巨大的数字 $N$ 转换为代数式。例如，如果 $N=100$，设 $m=4$，则 $100 = 4^3 + 2(4^2) + 4$。使用字母 $x$，将其变为 $f(x) = x^3 + 2x^2 + x$ 这样一个式子（里世界）。

这个式子有趣的地方在于，它具有 “只要将 $m$（上例中是4）代入字母 $x$，就随时能穿越回到现实的数字 $N$” 这一性质。

在两个世界同时寻找沙金

GNFS 会制造许多随意的整数对 $(a, b)$，并同时进行以下两个计算：

现实世界： $a - b \times m$
代数式世界：用代数式的规则计算出的 $a - b \times x$ 的值

通过将问题分为两个世界，所处理的数字尺寸就会剧烈减小（变轻）。这就像是把一块巨岩劈成两半，变成易于处理的石块的感觉。

然后，只有当 “在现实世界和代数式世界中，两边都『仅由小质数组成（沙金）』” 时，才用筛子把这种奇迹般的数对 $(a, b)$ 筛选出来并收集。这就是“数域筛选法”这个名字的由来。

密码终于被破译的瞬间

当从两个世界收集到数千万张“沙金卡片”后，就利用超级计算机庞大的矩阵计算，找出在第2章做过的“质数个数全部变成偶数的组合”。

找到组合后：

将在现实世界中形成的平方数设为 $X^2$
将在代数式世界中形成的平方代数式设为 $Y(x)^2$

最后，将 $m$ 代入代数式 $Y(x)$ 的 $x$ 中，使其穿越到现实世界并汇合。于是，就像数学魔法一样，“$X^2$ 和 $Y^2$ 的余数相同” 的状态就严密地完成了！

剩下的就如第1章所述，只要计算 $X - Y$ 和 $N$ 的最大公约数，坚不可摧的RSA密码就会轰然崩塌，秘密的质数就会显露出来。

结语：数学永无止境

你可能会想：“太好了，用 GNFS 就能破解任何密码了吧！” 但是，RSA 密码也没有认输。目前互联网上使用的是被称为“RSA-2048（约 617 位）”的怪物般的巨大数字。

不管 GNFS 作为人类最强算法有多厉害，据说仅仅是解开 270 位数（RSA-270），即使把全世界的计算机连接起来，也需要几千年、几万年。就目前而言，我们的 LINE 和银行数据是安全的。

然而，如果出现了 “无论多巨大的数字，都能瞬间找到 $X$ 和 $Y$ 的魔法”，那会怎么样呢？其实，最接近这种魔法的存在就是目前正在开发中的 “量子计算机（Shor 算法）”。在数学上已经证明，如果利用量子力学的波动性质，就能无视麻烦的卡片收集拼图，一击命中答案。

制造密码的人（防御）与制造破解密码算法的人（攻击）之间无止境的智慧较量。当你知道初中学到的“质因数分解”和“代数式”，其实是活跃在世界安全最前线激烈交锋的武器时，是不是觉得数学课稍微变得有趣了一点呢？

发现未来最强算法的，也许就是正在读这篇文章的你！

(※本文是为了向初中生概念化地展示密码破译的数学魅力而写的。实际的 GNFS 使用了代数域的理想类群、同态映射等高级大学数学知识进行严密计算。)