3

RSAアルゴリズムを検討しており、RSA公開鍵を因数分解するのにIntel i-7コア（@ 2.50 gHz）にかかる時間を知りたいと思います。

このために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(これは、平均して 2 倍の数をチェックする必要があるため、1 ビット多くするとランタイムが 2 倍になることを意味します)

45 ビットに 33 ミリ秒かかった場合、1024 ビットには約 10 ミリ秒かかります。2^1024 / 2^45 * 33ms = 5.34654 * 10^285 年。

もちろん、これは 1024 ビット コードが長い数値 (64 ビット?) のコードとまったく同じくらい効率的であることを前提としています。10^285 年は一般数体ふるいに切り替えてその時間の数百万年をスクラッチするのに十分な時間以上であることを考えると、これは大胆な声明です...

2009 年には、768 ビットの rsa-768 が、約 1000 コアと 2 年間の計算を使用してクラックされました。彼らが一般数体ふるいを使用したと仮定すると (非常に公正な仮定)、同じハードウェアを使用して 1024 ビットの数をクラックするには 7481 年かかります。

または、このアルゴリズムで i7 のみを使用すると、約 300 万年になります。まだまだお久しぶりです(;_;)

于 2013-01-13T12:34:52.750 に答える