You can use the Jacobi symbol for the Solovay–Strassen primality test. If an odd integer is prime, then the congruence
must hold for all integers . If there is an integer in such that the congruence relation is not satisfied, then is not prime.
Check if is prime or not. Choose and perform the primality test. Compare the two values in the congruence relation.
First calculate the left side of the congruence relation using the Jacobi symbol.
Calculate the right side of the congruence relation.
The integer is not prime since it does not satisfy the congruence relation for .
Next, check if is prime or not. Choose and perform the primality test.
The integer is probably prime since it satisfies the congruence relation for .
Perform the primality test for all in to confirm that the integer is indeed prime.
Verify the result with isprime
.