ソロベイ–シュトラッセン素数判定法
がnと互いに素な様々な底aに対して成立するかどうかを考えることができる。nが素数なら、この合同式はすべてのaに対して真である。そのため、ランダムにaを取ってこの合同式をチェックすれば、成り立たないaが存在した時にnが素数でないことが言える(ただし素因数分解は分からない)。この場合の底aをnのEuler witnessと呼ぶ。このaはnが合成数であることの証拠である。もしnが合成数で上の合同式が成立するならば、そのときの底aをnのEuler liarと呼ぶ。
任意の奇数の合成数nに対して、全ての底のうち少なくとも半分の底
a ∈ ( Z / n Z ) ∗ {\displaystyle a\in (\mathbb {Z} /n\mathbb {Z} )^{*}}
がEuler witnessである。これは、証拠の数がずっと少なくなり得るフェルマーテストとは対照的である。そのため、フェルマーテストにおけるカーマイケル数の存在とは対照的に、証拠がたくさん存在しないような(奇数の)合成数nは存在しない。
このアルゴリズムは以下の疑似コードで書ける:
冪剰余の高速なアルゴリズムを使えば、このアルゴリズムの実行時間はO(k·log n)である(kは異なるaでテストをする回数)。
( a n ) ( a i n ) = ( a ⋅ a i n ) {\displaystyle \left({\frac {a}{n}}\right)\left({\frac {a_{i}}{n}}\right)=\left({\frac {a\cdot a_{i}}{n}}\right)}
なので、
( a ⋅ a i ) ( n − 1 ) / 2 ≢ ( a ⋅ a i n ) ( mod n ) . {\displaystyle (a\cdot a_{i})^{(n-1)/2}\not \equiv \left({\frac {a\cdot a_{i}}{n}}\right){\pmod {n}}.}
が成り立つ。
これにより、各Euler liar aiに対して、a·aiがEuler witnessになる。そのため、Euler witnessの個数はEuler liarの個数以上である。それゆえ、nが合成数ならば、gcd(a,n) = 1となるaのうち少なくとも半分はEuler witnessである。
このため、失敗の確率は最大で2である(ミラー-ラビン素数判定法の失敗の確率(最大4)と比較されたい)。
暗号の目的で使用する場合、沢山のaでテストするほど、つまり十分大きなkを選べば、テストはより正確になる。そのためこのアルゴリズムが失敗する可能性はとても低いので、実用的な暗号への応用においてはこの方法で得られた(擬似)乱数が使われる。しかし、素数を得ることが重要であるような応用においては、ECPP(英語版)やPocklingtonのような素数性を「証明」するテストを使用すべきである。