ソロベイ–シュトラッセン素数判定法
このアルゴリズムは誤った答えを返すことがある。入力nが実際に素数であれば、出力は常に正しく「probably prime」である。しかし、入力nが合成数である場合にも、出力が「probably prime」である場合がある。そのような整数nは擬素数と呼ばれる。
nが奇数の合成数である場合、gcd(a,n) = 1であるようなaのうち少なくとも半分はEuler witnessである。これは以下のように証明できる。{a1, a2, ..., am}をEuler liarの集合とし、aをEuler witnessとする。各i = 1,2,...,mに対して次が成り立つ:
( a ⋅ a i ) ( n − 1 ) / 2 = a ( n − 1 ) / 2 ⋅ a i ( n − 1 ) / 2 = a ( n − 1 ) / 2 ⋅ ( a i n ) ≢ ( a n ) ( a i n ) ( mod n ) {\displaystyle (a\cdot a_{i})^{(n-1)/2}=a^{(n-1)/2}\cdot a_{i}^{(n-1)/2}=a^{(n-1)/2}\cdot \left({\frac {a_{i}}{n}}\right)\not \equiv \left({\frac {a}{n}}\right)\left({\frac {a_{i}}{n}}\right){\pmod {n}}}