烤糊的饼干

🍪 烤糊的孪生饼干

1. 为什么叫“孪生饼干”？

在数论里，孪生质数指相差为 2 的质数对（如 3 和 5， 11 和 13）。

但这里的厨师更懒，他选的 p=1013 和 q=1019 相差只有 6。

在 RSA 里，如果 p 和 q 挨得特别近，n 的平方根就会刚好卡在它们俩的正中间。这就像把钥匙藏在锁旁边的地毯下——根本不用暴力拆锁，掀开地毯就行。

2. 费马分解的数学魔术（手算推导）

费马分解的核心是一个恒等式：

如果 n 能写成两个数的平方差，那这两个数就是 p 和 q！

公式：

设

a = (p + q) / 2 （两个质数的中点）

b = (q - p) / 2 （中点到质数的距离）

那么：

a² - b² = (a-b)(a+b) = p * q = n

所以只要找到 a 和 b，让 a² - n = b² 成立，就分解成功了。

针对这道题，我们手算一遍：

已知 n = 1032247

1. 先对 n 开平方：

√1032247 ≈ 1015.996 （因为 1016² = 1032256）

所以我们从 a = 1016 开始试。

2. 计算 a² - n：

1016² = 1032256

1032256 - 1032247 = 9

3. 检查 9 是不是完全平方数：

√9 = 3，是整数！

所以 b = 3

4. 瞬间得到：

p = a - b = 1016 - 3 = 1013

q = a + b = 1016 + 3 = 1019

连循环都没进，这就是“孪生”的威力。