烤糊的饼干

烤糊的孪生饼干1. 为什么叫“孪生饼干”在数论里孪生质数指相差为 2 的质数对如 3 和 5 11 和 13。但这里的厨师更懒他选的 p1013 和 q1019 相差只有 6。在 RSA 里如果 p 和 q 挨得特别近n 的平方根就会刚好卡在它们俩的正中间。这就像把钥匙藏在锁旁边的地毯下——根本不用暴力拆锁掀开地毯就行。2. 费马分解的数学魔术手算推导费马分解的核心是一个恒等式如果 n 能写成两个数的平方差那这两个数就是 p 和 q公式设a (p q) / 2 两个质数的中点b (q - p) / 2 中点到质数的距离那么a² - b² (a-b)(ab) p * q n所以只要找到 a 和 b让 a² - n b² 成立就分解成功了。针对这道题我们手算一遍已知 n 10322471. 先对 n 开平方√1032247 ≈ 1015.996 因为 1016² 1032256所以我们从 a 1016 开始试。2. 计算 a² - n1016² 10322561032256 - 1032247 93. 检查 9 是不是完全平方数√9 3是整数所以 b 34. 瞬间得到p a - b 1016 - 3 1013q a b 1016 3 1019连循环都没进这就是“孪生”的威力。