素数性判定
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/31 00:03 UTC 版)
ヤコビ記号とルジャンドル記号が異なる別の方法がある。オイラーの規準の式が合成数を法として使用される場合、結果はヤコビ記号の値である場合とそうでない場合があり、実際には−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は「おそらく素数」（擬素数）である。 これは確率論的なソロベイ–シュトラッセン素数判定法と、Baillie-PSW primality testやミラー–ラビン素数判定法などの改良の基礎である。 間接的な使用として、リュカ–レーマー素数判定の実行中のエラー検出ルーチンとして使用することができる。これは現代のコンピュータハードウェアにおいても 2 82 , 589 , 933 − 1 {\displaystyle {\begin{aligned}2^{82,589,933}-1\end{aligned}}} （既知の最大のメルセンヌ素数）を処理を完了するのに数週間かかる場合がある。In nominal cases, the Jacobi symbol: ( s i − 2 M p ) = − 1 i ≠ 0 {\displaystyle {\begin{aligned}\left({\frac {s_{i}-2}{M_{p}}}\right)&=-1&i\neq 0\end{aligned}}} これは最終的な剰余 s p − 2 {\displaystyle {\begin{aligned}s_{p-2}\end{aligned}}} にも当てはまるため、妥当性の検証として使用できる。ただしハードウェアでエラーが生じた場合、結果が0または1になる可能性が50%あり、これは s {\displaystyle {\begin{aligned}s\end{aligned}}} の後続の項で変化しない（別のエラーが生じて-1に戻らない限り）。
※この「素数性判定」の解説は、「ヤコビ記号」の解説の一部です。
「素数性判定」を含む「ヤコビ記号」の記事については、「ヤコビ記号」の概要を参照ください。
- 素数性判定のページへのリンク
