Python RSA广播攻击中，二分查找求立方根为何使用比特长度？

先给出参考的立方根查找函数：

def find_cube_root(n):
    lo = 0
    hi = 1 << ((n.bit_length() + 2) // 3)
    while lo < hi:
        mid = (lo+hi)//2
        if mid**3 < n:
            lo = mid+1
        else:
            hi = mid
    return lo

这个函数用于从消息的三次方m³（即输入参数n = m³）中还原出原消息m。你的场景中，输入n的字节长度为454，比特长度为1507。

为什么比特长度的方法能正确设置上限？ #

核心是利用了整数比特长度和数值范围的对应关系：

• 一个数的bit_length()返回它的二进制位数（不含前导零），比如数值x满足2^(k-1) ≤ x < 2^k时，x.bit_length() = k。
• 已知n = m³，假设m的比特长度是k，那么2^(k-1) ≤ m < 2^k，两边立方后得到2^(3k-3) ≤ m³ < 2^(3k)。
• 对应到n的比特长度k_n，就有3k-3 ≤ k_n < 3k，整理后可得k = (k_n + 2) // 3（整数除法）。
• 因此1 << k（即2^k）是比m大的最小2的幂，完全覆盖了m的取值范围，而且这个上限的大小刚好合适，不会让二分查找的范围过大。

为什么用num//2或num//3作为上限会“无效”？ #

原因很简单：这两个值太大了，导致二分查找的效率低到不可用：

• 当n = m³时，m和n的差距是数量级的：比如m是一个500多比特的数，n就是1500多比特的数，n//2或n//3依然是1500比特左右的超大数，而m只有500多比特。
• 二分查找的次数和上限的比特长度正相关，用n//2作为上限需要约1500次循环，而比特长度方法只需要约500次。对于超大整数来说，每次循环里的mid**3计算成本极高，循环次数过多会直接导致程序运行超时、资源耗尽，看起来就像是“无效”。

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