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

 

This entry was posted in Uncategorized and tagged , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s