ヤコビ記号
これは確率論的なソロベイ–シュトラッセン素数判定法と、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に戻らない限り)。