3

拡張ユークリッドアルゴリズムは、素数pを法とする単一の数値の逆数を計算するための理想的な方法であることを私は知っています。

しかし、 A [x]がxの逆数を持つ配列Aを作成したい場合はどうなりますか？すべての要素の逆数を個別に計算するよりも、そのような配列を計算するより速い方法はありますか？

あなたは次のような多くのアイデンティティを持っているので、私は直感的にショートカットがあることを期待しています

A[x*y % p] = A[x]*A[y] % p

ただし、配列A全体を取得するための一般的な方法は考えられません。

4

3 に答える 3

3

逆関数の計算を半分にする簡単な方法は、を使用することです。

inverse(p - k) = p - inverse(k)

拡張ユークリッドアルゴリズムを使用して配列の前半のみを埋め、残りの半分を対称性で埋めます。

次の速度が速くなるかどうかはわかりませんが、計算は少なくて済みますが、配列へのアクセスパターンが悪いため、遅くなる可能性があります。

int A[p] = {0};
A[1] = 1;
for(int k = 2; k < p; ++k) {
    if (A[k] == 0) {
        // haven't found the inverse yet
        inv = inverse(k,p); // extended Euclidean algorithm or Fermat's theorem
        int m = k, i = inv;
        while(m != 1) {
            A[m] = i;
            m = (m*k) % p;
            i = (i*inv) % p;
        }
    }
}

逆数がまだわからない値に遭遇するたびに、要素ごとに2つのモジュラー乗算のみを使用して、その値によって生成されたサブグループ全体の逆数を繰り返し計算します（最初の逆関数を除く）。比較的すぐに、モジュロ単位のグループ全体のジェネレーターをヒットする必要がありますp。

于 2012-12-24T01:37:30.510 に答える
2

paプライムの場合、要素{1、2、3、...、（p-1）}は巡回群を形成します。つまり、{x ^ 0、x ^ 1、x ^ 2、...、x ^（p-2）}が集合であるような数（実際には多数）のxが存在します。xの逆関数を見つけたら、それをyと呼びます。これは、yを適切な累乗にするだけで、対応する逆関数を取得できます。y^kはx^kの逆関数です。どのようにしてそのようなxを見つけますか？ランダムな要素を選び、それを（p-1）/2の累乗に上げます。その数は1または-1（p-1）のいずれかになります。-1の場合、ジェネレーターがあります。要素を累乗することは、「二乗による指数化」を使用して行う必要があります。

于 2012-12-25T04:01:45.263 に答える
0

次のコードは、mod関数の定義から派生しています。

ここに画像の説明を入力してください

public long[] InverseTable(long n, long p)
{
    long[] inverse = new long[n+1];
    inverse[1] = 1;
    for (long i = 2; i <= n; i++)
        inverse[i] = p - (inverse[p % i] * (p / i) % p);
    return inverse;
}
于 2020-07-03T19:03:18.720 に答える