15.3.5 Jacobi記号の計算

[この節は廃止予定です。現在のJacobi記号のコードはもっと効率的なものに置き換わっています。]

mpz_jacobi関数とmpz_kronecker関数の現在の実装は，前述のGCDアルゴリズム (see Binary GCD)のところで述べた2進GCDアルゴリズムを簡易化したものを使っており，入力値が大きい値の時はさほど高速ではありません。 Lehmerのアルゴリズムや2進アルゴリズムを多段階にしたものを使えばマシになるかもしれません。

入力値が1リムで収まっている場合は，mpz_kronecker_ui関数やその周辺の関数でも同様ですが， 最初のリダクションはmpn_mod_1関数かmpn_modexact_1_odd関数を使って行われます。 これらは1リム対象の2進アルゴリズムを用いているもので，この場合については大変に効率的に実行できます。

テーブル参照や条件分岐を防ぐため，本ルーチン内では計算結果の符号変化については数ビット内に収まるように操作しています。