## Solovay-Strassen Test

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

To enhance this, we note that if *p* > 2 is prime, the value modulo *p* tells us whether *a* is a square modulo *p*. We had written extensively on this before – in short, the Legendre symbol satisfies:

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.

## Jacobi Symbol

Let us extend the Legendre symbol to the Jacobi symbol.

Definition.Let a be any integer and n be an odd positive integer. Write

be its prime factorization. The

Jacobi symbolis defined via:where each term is the Legendre symbol.

The Jacobi symbol inherits most properties of the Legendre symbol.

**Exercise**

Prove the following properties of the Jacobi symbol.

**Proof**

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

Solovay-Strassen Test.Given an odd and base , compute the Jacobi symbol . Now check that

and that both sides are non-zero.

### Example

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

but

In fact, the following is true in general.

Theorem.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.