3

我们正在研究 RSA 算法，想知道英特尔 i-7 内核 (@ 2.50 gHz) 分解 RSA 公钥需要多长时间。

我们为此写了一段java，不知道效果如何

public static String factorise(long l)
{
    double a = Math.floor(Math.sqrt(l));
    while(l/a != Math.round(l/a))
    {
        a--;
    }
    return (long)a + ", " + (long)(l/a);    
}

对于 2^45 左右的数字，PC 花费了大约 33 毫秒。理论上，分解一个 2^1024 左右的数需要多长时间？

提前致谢 ：）

4

1 回答 1

16

您的算法是 O(2^n)，其中 n 是原始数字中的位数l。a（这意味着多一点将使运行时间加倍，因为必须检查两倍的数字- 平均而言）

如果 45 位需要 33 毫秒，那么 1024 位将需要大约 1024 位。2^1024 / 2^45 * 33ms = 5.34654 * 10^285 年。

当然，这假设 1024 位代码与长数字（64 位？）的代码一样有效。这是一个大胆的声明，考虑到 10^285 年的时间足以切换到通用数域筛并刮掉那段时间的几百万年......

2009 年，使用大约 1000 个内核和 2 年的计算破解了 768 位数字 rsa-768。假设他们使用通用数字域筛（一个非常公平的假设），他们需要 7481 年才能使用相同的硬件破解 1024 位数字。

或者只使用你的 i7 和这个算法：大约 300 万年。还有很长一段时间.... ;)

于 2013-01-13T12:34:52.750 回答