在 Python RSA 广播攻击中，为什么我在二进制搜索立方根时使用位长度？

Question

https://stackoverflow.com/a/23622115/9481613

显示此功能：

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

³ 消息的立方体，这就是我需要这个函数的原因。

len(n)

结果是 454 对 1507 位长度。

我一直试图将

high

限制在

num // 2

或

num // 3

上，但这是行不通的。为什么位长在这里起作用？

Answer 1

该算法尝试使用

二分法

计算整数 n 的立方根。上下文是 Håstad 的广播攻击 的最后一步，其中

n

可以是数千位，如果事先一切顺利，预计正好是整数的立方。

为什么位长在这里起作用？

表情

hi = 1 << ((n.bit_length() + 2) // 3)

通过过量产生所需结果的粗略近似值。让我们证明这一点。

1. 对于整数

   n >= 0

   ，根据int.bit_length()的规范，

   n.bit_length()

   是最小的非负整数

   x

   使得

   n < 2**x

   .
2. 对于每个非负整数

   x

   ，如果成立

   x <= ((x + 2) // 3) * 3

3. 输入

   x

   产生

   2**x

   （即

   x

   ^th 次方的二）的函数是非递增的
4. 因此

   n < 2**(((x + 2) // 3) * 3)

5. 根据幂的标准属性，

   2**(((x + 2) // 3) * 3)

   是

   (2**((x + 2) // 3))**3

6. 对于每个非负整数

   i

   ，它成立

   (1 << i) == (2**i)

• 因此

  hi

  的初始值是这样的

  n < hi**3

  和

  hi >= 0

  .

二分算法的循环不变条件

lo <= hi  and  (lo-1)**3 < n  and  n <= hi**3

现在很容易通过归纳建立：它在 while 循环之前成立，并通过所做的更改来维护（证明使用上面的属性 3），因此在退出时有效。在这一点上，它进一步持有

lo >= hi

，因此在输出时函数返回最小整数

lo

使得

lo**3 >= n

，它是

n

的整数立方根。