Legendre Symbol
ルジャンドル記号 (a/p) は、a が素数 p を法とする平方剰余であるかを判定する記号である。値は 1（剰余である）、-1（剰余でない）、0（p が a を割り切る）のいずれかとなる。
目的
素数を法とする二次方程式の可解性を判定する。Tonelli-Shanks アルゴリズムの基礎となる。
メカニズム
(a/p) = a^((p-1)/2) mod p（オイラーの判定規準）。性質として (ab/p)=(a/p)(b/p) が成り立ち、(a/p)*(a/q) は平方剰余の相互法則に従う。これにより x^2≡a (mod p) が解を持つかどうかを判定できる。
ユースケース
- 平方剰余かどうかの判定
- 数論アルゴリズム
- 暗号技術（クリプトグラフィ）への応用