# A little intro to the Jacobi symbol: Part 3

Posted by Jason Polak on 27. July 2018 · Write a comment · Categories: number-theory · Tags: , , ,

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)$.
More »

# Miller-Rabin Primality Test

Posted by Jason Polak on 09. May 2018 · Write a comment · Categories: number-theory · Tags: , ,

Fermat's little theorem states that for a prime number $p$, any $a\in \Z/p^\times$ satisfies $a^{p-1} = 1$. If $p$ is not prime, this may not necessarily be true. For example:
$$2^{402} = 376 \in \Z/403^\times.$$
Therefore, we can conclude that 403 is not a prime number. In fact, $403 = 13\cdot 31$ Fermat's little theorem can be used as a test for compositeness this way: if you can find a number $a$ relatively prime to $p$ such that $a^{p-1} \not\equiv 1\pmod{p}$, then $p$ is actually composite.

If there exists an $a\in\{1,\dots,p-1\}$ with $a^{p-1}\not\equiv 1\pmod{p}$, then $a$ is called a Fermat witness to the compositeness of $p$. That is, it proves that $p$ is composite. Notice that we do not require $a$ to be relatively prime to $p$ in this definition of a Fermat witness: if any number $a\lt p$ exists with $a^{p-1}\not\equiv 1\pmod{p}$, then $p$ cannot be prime, because if it were, $a$ would actually be relatively prime to $p$ and this would contradict Fermat's little theorem.

Fermat's little theorem is a pretty good test for compositeness: if $p$ is some odd composite integer with at least one relatively prime Fermat witness, then at least half the numbers in the range $2,3,\dots,p-2$ will also be witnesses. Note: we are using this range because $p-1$ and $1$ aren't witnesses. Therefore, you can use Fermat's little theorem as a randomized prime-testing algorithm: randomly select elements $a$ from $\{2,\dots,p-2\}$ and check if they satisfy $a^{p-1} = 1\pmod{p}$. Therefore, if you have some large number $N$ that is composite and has at least one witness, a randomised Fermat's little theorem algorithm randomly testing $K$ different bases in $\{2,\dots,N-1\}$ will have probability of less than $1/2^K$ at failing to detect that $N$ is composite.
More »