A little intro to the Jacobi symbol: Part 3

This is the final post on the Jacobi symbol. Recall that the Jacobi symbol $(m/n)$ for relatively prime integers $m$ and $n$ is defined to be the sign of the permutation $x\mapsto mx$ on the ring $\Z/n$. In the introductory post we saw this definition, some examples, and basic properties for calculation purposes.

In Part 2 we saw that for an odd prime $p$ and an integer $a$ that is relatively prime to $p$, the Jacobi symbol $(a/p) = 1$ if and only if $a$ is a square modulo $p$ (a “quadratic residue”). The basic properties of the Jacobi symbol then give the classic law of quadratic reciprocity.

Now, we’re going to see one last application of the Jacobi symbol: primality testing in what’s called the Solovay-Strassen primality test. How does it work? It starts with an observation we saw before: in the ring $\Z/p$, there exists a primitive element $g\in \Z/p$. It is an element that generates the multiplicative cyclic group $\Z/p^\times\cong \Z/(p-1)$.

The existence of such a $g$ implies Euler’s criterion.

Theorem.Let $p$ be an odd prime. If $a$ is an integer relatively prime to $p$ then $a^{(p-1)/2}\equiv 1\pmod{p}$ if $a$ is a square modulo $p$. Otherwise $a^{(p-1)/2}\equiv -1\pmod{p}$.

The proof is straightforward: use the primitive element $g$, write $g^k = a$ for some $k$. Then $a$ is a quadratic residue if and only if $k$ is even, and then Euler’s theorem follows by direct calculation.

Now we have two ways of determining whether $a$ is a square modulo $p$: either compute the Jacobi symbol $(a/p)$ or the modular exponentiation $a^{(p-1)/2}$. Both can be done quickly. The key to the Solovay-Strassen test is that both have the same sign. Therefore, if $p$ is an odd prime, each element of $\{1,2,\dots,p-1\}$ will satisfy
$$(a/p)a^{(p-1)/2} \equiv 1\pmod{p}.$$
Thus, the Solovay-Strassen randomized primality test should proceed as follows: choose a random element $a\in \{1,2,\dots,p-1\}$ and compute the quantity
If this is anything else than 1, then the number $p$ cannot be prime. If this quantity is 1 after repeating many times, the the number $p$ is probably prime.

This test is better than using Fermat’s little theorem alone, since it’s possible to prove that at least half the numbers in $\{1,2,\dots,p-1\}$ will prove a composite odd number composite with the Solovay-Strassen test.

Leave a comment

Fields marked with * are required. LaTeX snippets may be entered by surrounding them with single dollar signs. Use double dollar signs for display equations.