Primality Tests III

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 $a^{(n-1)/2} \equiv \pm 1 \pmod n.$

To enhance this, we note that if p > 2 is prime, the value $a^{\frac{p-1}2}$ modulo p tells us whether a is a square modulo p. We had written extensively on this before – in short, the Legendre symbol $(\frac a p) := a^{\frac{p-1} 2} \mod p$ satisfies:

$\left( \frac a p\right) = \begin{cases} +1, \quad &\text{if } a \text{ is a quadratic residue modulo } p\\ -1, \quad &\text{if } a \text{ is a non-quadratic residue modulo } p\\0, \quad &\text{if } a \text{ is divisible by } p\end{cases}$

$\left( \frac {-1} p\right) = \begin{cases} 1,\quad&\text{if } p\equiv 1 \pmod 4,\\ -1,\quad &\text{if }p \equiv -1\pmod 4.\end{cases}$

$\left( \frac 2 p\right) = \begin{cases} 1,\quad &\text{if } p\equiv 1, 7\pmod 8,\\ -1, \quad &\text{if } p \equiv 3, 5\pmod 8.\end{cases}$

$\left( \frac{ab} p\right) = \left( \frac a p\right) \left( \frac b p\right).$

$a \equiv b \pmod p \implies \left( \frac a p\right) = \left( \frac b p\right).$

$p, q \text{ odd prime} \implies \left( \frac q p\right) = (-1)^{\frac{p-1}2 \frac{q-1} 2}\left( \frac p q\right).$

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 $(\frac a p)$ and extend its definition to $(\frac a n)$ , we could compute $a^{\frac {n-1}2} \mod n$ and compare the two.

blue-lin

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

$n = p_1^{r_1} p_2^{r_2} \ldots p_d^{r_d}$

be its prime factorization. The Jacobi symbol is defined via:

$\left(\frac a n\right) := \left(\frac a {p_1}\right)^{r_1} \left(\frac a {p_2}\right)^{r_2} \ldots \left(\frac a {p_d}\right)^{r_d}$

where each term $\left(\frac a {p_i}\right)$ is the Legendre symbol.

The Jacobi symbol inherits most properties of the Legendre symbol.

Exercise

Prove the following properties of the Jacobi symbol.

$\left( \frac {-1} n\right) = \begin{cases} 1,\quad&\text{if } n\equiv 1 \pmod 4,\\ -1,\quad &\text{if }n \equiv -1\pmod 4.\end{cases}$

$\left( \frac 2 n\right) = \begin{cases} 1,\quad &\text{if } n\equiv 1, 7\pmod 8,\\ -1, \quad &\text{if } n \equiv 3, 5\pmod 8.\end{cases}$

$\left( \frac{ab} n\right) = \left( \frac a n\right) \left( \frac b n\right).$

$a \equiv b \pmod n \implies \left(\frac a n\right) = \left(\frac b n\right).$

$m, n \text{ odd positive} \implies \left( \frac n m\right) = (-1)^{\frac{m-1}2 \frac{n-1} 2}\left( \frac m n\right).$

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 $(\frac a n)(\frac b n) = (\frac {ab} n)$ and $(\frac a {mn}) = (\frac a m)(\frac a n)$ it suffices to define, for positive odd m and n,

$D(m, n) = (-1)^{\frac {m-1}2\frac {n-1}2}$

and prove $D(mm', n) = D(m, n)D(m',n)$ and $D(m, nn') = D(m,n) D(m,n').$ The two claims are identical, so let’s just show the first, which is equivalent to:

$\frac{mm' - 1}2 \frac{n-1}2 \equiv \frac {m-1}2 \frac{n-1}2 + \frac{m'-1}2 \frac{n-1}2 \pmod 2.$

But this is obvious: the difference between the two sides is $\frac{(m-1)(m'-1)}2 \frac{n-1}2$ which is clearly even. ♦

blue-lin

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 $(\frac {69}{133})$ we repeatedly apply the above properties to obtain:

$(\frac{33}{89}) = (\frac{89}{33}) = (\frac{23}{33}) = (\frac{33}{23}) = (\frac{10}{23}) = (\frac 2 {23})(\frac 5 {23}) = (\frac 5 {23}) = (\frac {23} 5) = (\frac 3 5) = (\frac 5 3) = (\frac 2 3) = -1.$

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.

blue-lin

Description of Test

Solovay-Strassen Test.

Given an odd $n$ and base $a$ , compute the Jacobi symbol $(\frac a n)$ . Now check that

$a^{\frac{n-1} 2} \equiv (\frac a n) \pmod n$

and that both sides are non-zero.

Example

Let n = 10261 and a = 2. Immediately the Jacobi symbol gives $(\frac a n) = -1$ . On the other hand, $a^{\frac {n-1}2}\equiv 1 \pmod n.$ 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

$2^{(n-1)/4} \equiv 1985 \not\equiv \pm 1 \pmod n$ but $2^{(n-1)/2} \equiv 1 \pmod n.$

In fact, the following is true in general.

Theorem.

If odd $n$ passes the Rabin-Miller test to base $a$ , 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.

blue-lin