如何分解2048位RSA模数n为位半段交换的素数p、q？

已知2048位模数n = p*q，其中p和q是1024位素数，且p是q的位半段交换结果（即p = r||s，q = s||r，r和s均为512位二进制数），暴力遍历不可行，可通过以下数学推导+高效算法解决：

核心数学推导 #

设M = 2^512（对应512位左移操作），则：

• p = r*M + s
• q = s*M + r

将p和q代入n = p*q并展开，结合模运算特性可得：
p ≡ -q mod (M+1)，进一步推导得p² ≡ -n mod (M+1)。

这一关键结论说明：p必然是-n在模M+1下的二次剩余的平方根，这是缩小候选范围的核心依据。

具体步骤 #

1. 定义关键常量
   计算M = 2^512，K = M + 1，L = M - 1（均为大整数，Python可直接处理）。

2. 计算二次剩余目标值
   计算C = (-n) % K，即-n模K的结果。

3. 求模K下的平方根
   使用Tonelli-Shanks算法求解x，使得x² ≡ C mod K。由于模K的二次剩余最多有2个平方根（x和K-x），候选值数量极少。

4. 定位候选p值
   计算p0 = int(n**0.5)（n的平方根，接近真实p的值），然后找到最接近p0且满足p ≡ x mod K或p ≡ (K-x) mod K的整数p。

5. 验证候选因子

   • 检查n % p == 0：若成立，则q = n // p。
   • 验证位半段交换关系：将p转换为1024位二进制字符串，分割为前512位（r）和后512位（s），交换后得到的二进制字符串转换为整数应等于q。
   • 可选：用Miller-Rabin素性测试确认p和q均为素数。

为什么这可行？ #

暴力遍历的复杂度是O(2^512)，完全不可行；而上述方法通过数学推导将候选p的数量缩小到2个左右，后续验证仅需几次大整数运算和素性测试，对于2048位n可在短时间内完成。

内容的提问来源于stack exchange，提问作者Javier