ヤコビ記号

さまざまなk（列）とn（行）でのヤコビ記号 。後述する規則(2)によりkはnを法として小さくすることができるため、 の場合のみ示す。平方剰余は黄色で強調される。-1のヤコビ記号となる数は平方剰余ではなく、"k" が互いに素なnを法とする平方剰余である場合、 となる。しかし、ヤコビ記号が1となる数（ と の列参照）は全てが平方剰余ではないことに注意。また、"n" または "k" のいずれかが平方数である場合、すべての値が非負となることに注意。
ヤコビ記号は、ルジャンドル記号の一般化である。ヤコビにより1837年に導入された。合同算術や数論の他の分野で理論的に興味深いものであるが、主な用途は計算数論、特に素数判定及び素因数分解である。これらは暗号理論においても重要である。
定義.
任意の整数 "a" と任意の正の奇整数 "n" に対して、ヤコビ記号 は "n" の素因数に対応するルジャンドル記号の積として定義される。
ここで
は"n"の素因数分解である。
ルジャンドル記号 は全ての整数 "a" と全ての奇素数 "p" に対して次のように定義される。
空積での通常の慣例に従い、 = 1とする。
下の引数が奇素数である場合、ヤコビ記号はルジャンドル記号と同じである。
表.
"n" ≤ 59, "k" ≤ 30で "n" が奇数のときのヤコビ記号 の値の表
性質.
以下の事実は、ヤコビ記号の定義とルジャンドル記号の対応する性質からの直接的推論である。
ヤコビ記号は上の引数（「分子」）が整数で下の引数（「分母」）が正の奇整数である場合にのみ定義される。
上または下の引数のいずれかが固定の場合、ヤコビ記号はもう一方の引数において完全乗法的関数になる。
平方剰余の法則: "m" と "n" が奇数で互いに素な正整数である場合、
であり、補足として
性質4と8を組み合わせると
となる。ルジャンドル記号と同様に、
但し、ルジャンドル記号と異なり、
これは、"a" が "n" を法とする平方剰余であるためには、"n" の全ての素因数を法とする平方剰余でなければならないためである。ただし、例えば "a" が "n" の素因数のちょうど2つを法とする非剰余である場合、ヤコビ記号は1に等しくなる。
ヤコビ記号は、平方と非平方の観点から一律に解釈することはできないが、ゾロタレフの補題()による順列の符号として一律に解釈することはできる。
ヤコビ記号は、法"n"に対するディリクレ指標である。
ヤコビ記号の計算.
上記の式は、2つの数のgcdを見つけるためにユークリッドの互除法に似た、ヤコビ記号を計算するための効率的な につながる（これは規則2に照らすと驚くべきことはない）。
Luaでの実装.
function jacobi(n, k)
 assert(k > 0 and k % 2 == 1)
 n = n % k
 t = 1
 while n ~= 0 do
 while n % 2 == 0 do
 n = n / 2
 r = k % 8
 if r == 3 or r == 5 then
 t = -t
 end
 end
 n, k = k, n
 if n % 4 == 3 and k % 4 == 3 then
 t = -t
 end
 n = n % k
 end
 if k == 1 then
 return t
 else
 return 0
 end
end
計算例.
ルジャンドル記号は奇素数 "p" に対してのみ定義され、ヤコビ記号と同じ規則に従う（つまり、 と の相互作用と補足式、および「分子」の乗法性）
問題: 素数9907が与えられたとする。を計算せよ。
ヤコビ記号を使用する.
2つの計算の違いは、ルジャンドル記号を使用する場合、記号を反転する前に「分子」を素数冪に因数分解する必要があることである。これにより、整数を因数分解するための既知の多項式時間アルゴリズムがないため、ルジャンドル記号を使用した計算はヤコビ記号を使用した計算よりも大幅に遅くなる。実際、これがヤコビがこの記号を導入した理由である。
素数性判定.
ヤコビ記号とルジャンドル記号が異なる別の方法がある。オイラーの規準の式が合成数を法として使用される場合、結果はヤコビ記号の値である場合とそうでない場合があり、実際には−1または1でさえないこともある。
そのため、数nが素数であるか合成数であるかが不明である場合は、乱数aを選択し、ヤコビ記号を計算し、オイラーの式と比較する。それらがnを法として異なる場合、nは合成数である。それらがaの多くの異なる値に対してnを法とする同じ剰余を持つ場合、nは「おそらく素数」（擬素数）である。
これは確率論的なソロベイ–シュトラッセン素数判定法と、やミラー–ラビン素数判定法などの改良の基礎である。
間接的な使用として、リュカ–レーマー素数判定の実行中のエラー検出ルーチンとして使用することができる。これは現代のコンピュータハードウェアにおいてもformula_15 （既知の最大のメルセンヌ素数）を処理を完了するのに数週間かかる場合がある。In nominal cases, the Jacobi symbol:
formula_16
これは最終的な剰余 formula_17 にも当てはまるため、妥当性の検証として使用できる。ただしハードウェアでエラーが生じた場合、結果が0または1になる可能性が50%あり、これは formula_18 の後続の項で変化しない（別のエラーが生じて-1に戻らない限り）。