逆関数の計算を半分にする簡単な方法は、を使用することです。
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
。