Solovay-Strassen primality test
= Solovay-Strassen primality test
{c}
{wiki=Solovay–Strassen_primality_test}
The Solovay-Strassen primality test samples unit bases and rejects an odd candidate as composite when it finds an <Euler witness>. Every prime passes every base by <Euler's criterion>, while an odd composite passes a random base with probability at most one half.