2

次のアルゴリズムの時間計算量を計算してみます。

private void encrypt()
{
        M = new BigInteger(64,random);
        C = M.multiply(k).mod(N); // O(n^2)    
}

private void decrypt()
{
        kk= k.modinverse(N); // O(n^3)
        Mp = kk.multiply(c).mod(N); //O(n^2)
}

時間の複雑さを正しく計算しましたか?

暗号化の時間計算量は O(n^2)、復号化の時間計算量は O(n^3) + O(n^2) = O(n^3) です。

4

1 に答える 1

2

分析がより詳細になり、数の乗算により適切な範囲が使用される可能性があります。使用された手順の複雑さをどこで得たのかについて、さらに詳しく説明する必要があります。

大きな数を乗算するには、カラツバ アルゴリズムまたはSchönhage–Strassen アルゴリズムを使用して、O(n^1.585)またはそれ以下にすることができます (詳細については、リンクされたウィキペディアのページを参照してください)。

新しい整数を構築し、モジュロで結果を計算することNは、線形よりも複雑ではありません。

したがって、encrypt手順の複雑さは、選択した乗算アルゴリズムに依存します。

decrypt()手続きについても同様です。のどこで複雑になったのかわかりませんmodinverse。剰余乗法逆行列は最大 で計算できますO(n^2)。

モジュラー逆数のウィキペディアのページで与えられた複雑さは として与えられO(log(M)^2)、これは数値の値を使用して表され、そのために逆数を計算します。あなたの分析は（数論アルゴリズムを扱うときに通常行われるように）、その値の代わりに数の長さを使用するため、複雑さが生じますO(N^2)。

于 2013-01-30T23:35:00.137 に答える