Jacobi Symbol
ヤコビ記号（Jacobi Symbol）は、ルジャンドル記号を合成数の法へ拡張したものである。n=∏p_i のとき (a/n)=∏(a/p_i) となる。
目的
平方剰余の判定を合成数の法へ拡張する。素数判定や数論アルゴリズムで使われる。
メカニズム
n を素因数分解せずに、平方相互法則とヤコビ記号の性質により効率的に計算できる。(a/n)=1 でも a が n を法とする平方剰余であることは保証されない（−1 なら非剰余と証明される）。Solovay-Strassen 素数判定がヤコビ記号を使う。
ユースケース
- 素数判定のテスト
- 平方剰余（クアドラティック）
- 数論アルゴリズム