ヤコビ記号
ヤコビ記号とルジャンドル記号が異なる別の方法がある。オイラーの規準の式が合成数を法として使用される場合、結果はヤコビ記号の値である場合とそうでない場合があり、実際には−1または1でさえないこともある。
( 19 45 ) = 1 and 19 45 − 1 2 ≡ 1 ( mod 45 ) . ( 8 21 ) = − 1 but 8 21 − 1 2 ≡ 1 ( mod 21 ) . ( 5 21 ) = 1 but 5 21 − 1 2 ≡ 16 ( mod 21 ) . {\displaystyle {\begin{aligned}\left({\frac {19}{45}}\right)&=1&&{\text{ and }}&19^{\frac {45-1}{2}}&\equiv 1{\pmod {45}}.\\\left({\frac {8}{21}}\right)&=-1&&{\text{ but }}&8^{\frac {21-1}{2}}&\equiv 1{\pmod {21}}.\\\left({\frac {5}{21}}\right)&=1&&{\text{ but }}&5^{\frac {21-1}{2}}&\equiv 16{\pmod {21}}.\end{aligned}}}
そのため、数nが素数であるか合成数であるかが不明である場合は、乱数aを選択し、ヤコビ記号(a/n)を計算し、オイラーの式と比較する。それらがnを法として異なる場合、nは合成数である。それらがaの多くの異なる値に対してnを法とする同じ剰余を持つ場合、nは「おそらく素数」(擬素数)である。
さまざまなk(列)とn(行)でのヤコビ記号 (k/n) 。後述する規則(2)によりkはnを法として小さくすることができるため、0 ≤ k < n の場合のみ示す。平方剰余は黄色で強調される。-1のヤコビ記号となる数は平方剰余ではなく、k が互いに素なnを法とする平方剰余である場合、 (k/n) = 1となる。しかし、ヤコビ記号が1となる数(n = 9 と n = 15 の列参照)は全てが平方剰余ではないことに注意。また、n または k のいずれかが平方数である場合、すべての値が非負となることに注意。
ヤコビ記号は、ルジャンドル記号の一般化である。ヤコビにより1837年に導入された。合同算術や数論の他の分野で理論的に興味深いものであるが、主な用途は計算数論、特に素数判定及び素因数分解である。これらは暗号理論においても重要である。
( 1001 9907 ) = ( 7 9907 ) ( 11 9907 ) ( 13 9907 ) . ( 7 9907 ) = − ( 9907 7 ) = − ( 2 7 ) = − 1. ( 11 9907 ) = − ( 9907 11 ) = − ( 7 11 ) = ( 11 7 ) = ( 4 7 ) = 1. ( 13 9907 ) = ( 9907 13 ) = ( 1 13 ) = 1. ( 1001 9907 ) = − 1.