algorithm - 大数のモジュラスべき乗

Question

SAFER+ アルゴリズムを実装しようとしています。このアルゴリズムでは、べき乗関数の係数を次のように求める必要があります。

pow(45, x) mod 257

変数 x はバイトであるため、0 から 255 の範囲になります。したがって、32 ビットまたは 64 ビットの整数を使用して実装すると、累乗関数の結果が非常に大きくなり、正しくない値になる可能性があります。

どうすればこの計算を実行できますか?

Answer 1

いくつかの擬似コード

function powermod(base, exponent, modulus) {
    if (base < 1 || exponent < 0 || modulus < 1)
        return -1

    result = 1;
    while (exponent > 0) {
       if ((exponent % 2) == 1) {
           result = (result * base) % modulus;
       }
       base = (base * base) % modulus;
       exponent = floor(exponent / 2);
    }
    return result;
}

そして電話する

powermod(45, x, 257)    

Answer 2

二乗を繰り返して累乗を実行し、各操作の後に係数を減らします。これは非常に標準的な手法です。

実際の例: 45^13 mod 257:

1. 最初に 45^2、45^4、45^8 mod 257 を計算します。

   45^2 mod 257 = 2025 mod 257 = 226

   45^4 mod 257 = 226^2 mod 257 = 51076 mod 257 = 190

   45^8 mod 257 = 190^2 mod 257 = 36100 mod 257 = 120

2. 次に、13 のバイナリ展開を使用してこれらを結合し、結果を取得します。

   45^13 mod 257 = 45^1 * 45^4 * 45^8 mod 257

   45^13 mod 257 = 45 * 190 * 120 mod 257

   45^13 mod 257 = 8550 * 120 mod 257

   45^13 mod 257 = 69 * 120 mod 257

   45^13 mod 257 = 8280 mod 257

   45^13 mod 257 = 56

計算の中間結果が 257*257 を超えることはないので、これは 32 ビット整数型で簡単に実行できることに注意してください。

Answer 3

基本的なアプローチは、指数ビットに応じて 2 乗または乗算し、各ステップでモジュラー リダクションを実行することです。このアルゴリズムは(2 進) 剰余累乗と呼ばれます。

Answer 4

単純なアイデンティティを考えてみましょう:

mod(A^2,p) = mod(A,p)*mod(A,p)

また、

A^4 = (A^2)^2

計算したい最終指数のバイナリ表現がわかっている場合、他のべき乗は簡単に計算されます。