ソロベイ–シュトラッセン素数判定法
レオンハルト・オイラーは任意の素数pと整数aに対して、
a ( p − 1 ) / 2 ≡ ( a p ) ( mod p ) {\displaystyle a^{(p-1)/2}\equiv \left({\frac {a}{p}}\right){\pmod {p}}}
( ( a p ) {\displaystyle \left({\tfrac {a}{p}}\right)} はルジャンドル指標(英語版))であることを証明した。ヤコビ指標(英語版)はルジャンドル指標を一般の奇数nに対する ( a n ) {\displaystyle \left({\tfrac {a}{n}}\right)} に一般化したものである。ヤコビ指標は平方剰余の相互法則のヤコビによる一般化を用いればO((log n))時間で計算できる。
奇数nが与えられたとき、合同式
a ( n − 1 ) / 2 ≡ ( a n ) ( mod n ) {\displaystyle a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}}
ソロベイ–シュトラッセン素数判定法(英: Solovay–Strassen primality test)は、Robert M. Solovay(英語版)とフォルカー・シュトラッセンによって開発された、与えられた数が合成数か擬素数か判定する確率的テストである。現在ではBaillie–PSW primality test(英語版)やミラー-ラビン素数判定法にとって代わられているが、RSA暗号の実用性を示したアルゴリズムとして歴史的には重要である。