5

私はこのリンクをウィキペディアの多数のモジュロから研究してきました。ここに疑似コードがあります。

function modular_pow(base, exponent, modulus)
    result := 1
    while exponent > 0
        if (exponent mod 2 == 1):
           result := (result * base) mod modulus
        exponent := exponent >> 1
        base = (base * base) mod modulus
    return result

wiki の説明がわかりません。exp%2 が偶数か奇数かを確認する必要があるのはなぜですか。また、なぜ私は3つの操作を行っているのですか?

4

1 に答える 1

4

このアルゴリズムは、Exponentiation by Squaringアルゴリズムとモジュロ演算を組み合わせたものです。

何が起こっているのかを理解するために、まずexponentが のべき乗である状況を考えてみましょう2。次に、 と仮定するexponent = 2 ^ kと、結果は結果k時間を二乗することで計算できます。つまり、

res = (...((base ^ 2) ^2 ) ... ) ^2))
              ---------------------
                     k times

exponentが の累乗でない場合2、追加の乗算を行う必要があります。exponent余りなく 2 で割ることができれば、底を 2 乗し、指数を割ることができます。ただし、余りがある場合は、中間結果に現在の値をさらに掛ける必要がありますbase。

表示されるのは、モジュロ乗算に適用される 2 乗による同じ累乗です。このアルゴリズムはexponent >> 1、 と同じ操作を使用して、2 による整数除算を示しfloor(exponent / 2)ます。

于 2013-11-07T15:22:22.150 に答える