This is an enhancement of the Euler test. Be forewarned that it is in fact weaker than the Rabin-Miller test so it may not be of much practical interest. Nevertheless, it’s included here for completeness.
Recall that to perform the Euler test on an odd n, we pick a base a and check if
Observe that the second, fourth and fifth properties follow easily from the definition of the Legendre symbol. The last property, known as the quadratic reciprocity law, is highly non-trivial and is the seed of an extremely deep area of algebraic number theory, called class field theory. But that’s a story for another day.
Now, if we had another way to compute the Legendre symbol and extend its definition to , we could compute and compare the two.
Let us extend the Legendre symbol to the Jacobi symbol.
Let a be any integer and n be an odd positive integer. Write
be its prime factorization. The Jacobi symbol is defined via:
where each term is the Legendre symbol.
The Jacobi symbol inherits most properties of the Legendre symbol.
Prove the following properties of the Jacobi symbol.
We will only prove the last property as an example. First note that when m and n are odd primes, the result is just the quadratic reciprocity theorem. Since we have and it suffices to define, for positive odd m and n,
and prove and The two claims are identical, so let’s just show the first, which is equivalent to:
But this is obvious: the difference between the two sides is which is clearly even. ♦
Computing the Jacobi Symbol
We thus have a computationally feasible way to compute the Jacobi symbol recursively for extremely large integers. E.g. to compute we repeatedly apply the above properties to obtain:
In Python code, we have:
def jacobi(m, n): if m == 0: return 0 if m == 1: return 1 if m < 0: if (n%4 == 3): return -jacobi(-m, n) else: return +jacobi(-m, n) if (m >= n): return jacobi(m%n, n) if m % 2 == 0: if (n%8 == 3 or n%8 == 5): return -jacobi(m/2, n) else: return +jacobi(m/2, n) if m % 4 == 3 and n % 4 == 3: return -jacobi(n, m) else: return jacobi(n, m)
Now we can describe our main objective.
Description of Test
Given an odd and base , compute the Jacobi symbol . Now check that
and that both sides are non-zero.
Let n = 10261 and a = 2. Immediately the Jacobi symbol gives . On the other hand, Thus even though n passes the Euler test for base 2, it fails the Solovay-Strassen test for the same base.
Notice that this also fails the Rabin-Miller test for the same base since
In fact, the following is true in general.
If odd passes the Rabin-Miller test to base , then it also passes the Solovay-Strassen test to the same base.
For a proof of the result, see theorem 3 of this paper. This is why we said there’s not much practical application for this test.