NTIC Some Surprising Applications of QR

Section 17.5 Some Surprising Applications of QR

What else can quadratic reciprocity do? The answer is, a lot. This section collates various interesting applications of QR as well as some places quadratic residues are more generally helpful.

🔗

Subsection 17.5.1 Factoring, briefly

🔗

As an example, it can help us with factoring large integers

$n\text{;}$ Gauss used it. The process itself is a little too long to describe here, but it's important to get the flavor.

🔗

The essential idea is that if

$a$ is a QR of

$n\text{,}$ then

$a$ is a QR of any prime

$p\mid n\text{.}$ QRs often have congruence conditions associated with them, so

$n$ must obey all of the congruence conditions for

$\left(\frac{a}{p}\right)$ for all the

$p$ which divide it. This might be a lot of conditions, which narrows the field considerably.

🔗

Then we can use a variant on the Fermat factoring method to check for possible

$a$ for which a prime divisor

$p$ of

$n$ definitely is or definitely is not a QR (again, quadratic reciprocity can help), and then one can compute Legendre/Jacobi symbols of possible

$p\mid n$ to reduce to just having to check a very few bigger possible prime factors.

🔗

Subsection 17.5.2 Primality testing

🔗

Another application is that it can help us check primality.

🔗

A specific example where it is helpful is with the so-called Fermat numbers. Recall (Subsection 12.1.1) that Euler blasted the following conjecture of Fermat's out of the water by disproving it for

$n=5\text{:}$

$\begin{equation*} F_n=2^{2^n}+1\text{ is always prime for }n\geq 0\text{.} \end{equation*}$

🔗

But what about bigger

$F_n\text{;}$ surely they are inaccessible to the usual factoring techniques?

🔗

Analogously to Mersenne numbers (Subsection 12.1.3), for which the Lucas-Lehmer test can check for primality (remember GIMPS?), there is a test called Pépin's test which can check for primality of Fermat numbers. (Pépin did this work in the late 1800s.) It turns out that no bigger Fermat numbers have turned out to be prime, all the way through

$n=31\text{.}$ See the relevant member of the excellent Prime Pages for more information.

🔗

Here is the test implemented naively in Sage:

xxxxxxxxxx
 
@interact
def _(n=(1,[1..6])):
    F=2^(2^n)+1
    pretty_print(html("The $%s$th Fermat number is $%s$"%(n,F)))
    test = mod(3,F)^((F-1)/2)
    if test == -1:
        pretty_print(html(r"Since $3^{(%s-1)/2}\equiv %s$, this Fermat number is prime"%(F,test)))
    else:
        pretty_print(html(r"Since $3^{(%s-1)/2}\equiv %s$, this Fermat number is not prime"%(F,test)))

🔗

You can already see from this code that it is checking Euler's criterion modulo

$F_n\text{,}$ and looking for a negative answer. Why would this test primality? Let's formally state and prove the criterion.

🔗

Fact 17.5.1. Pépin's Test.

For $n> 0\text{,}$ $F_n=2^{2^n}+1$ is prime exactly when

$\begin{equation*} 3^{2^{2^n-1}}\equiv -1\text{ (mod }2^{2^n}+1) \end{equation*}$

🔗

Proof.

We will try to connect this with Euler's Criterion. Note that $(F_n-1)/2 = 2^{2^n-1}\text{,}$ the power of three in the statement.

First, let's assume $F_n$ is prime. Since $F_n$ is one more than a multiple of four, clearly

\begin{equation*} F_n\equiv 1, 5,\text{ or }9\text{ (mod }12)\text{.} \end{equation*}

Let's examine a few cases.

If $F_n\equiv 1\text{ (mod }12)\text{,}$ then $3\mid 2^{2^n}=F_n-1\text{,}$ which cannot be true.
If $F_n\equiv 9\text{ (mod }12)\text{,}$ then $F_n$ is a number greater than three which is divisible by three – but it's prime, so that's not possible.
So $F_n\equiv 5\text{ (mod }12).$

Since $F_n$ is prime, that means by Proposition 17.3.4 we know $3$ is not a QR mod $F_n\text{.}$ Thus Theorem 16.5.2 should give $-1\text{.}$

For the converse, let's assume that Euler's Criterion gives this answer of $-1$ for $a=3\text{.}$ Then square both sides to get

\begin{equation*} 3^{F_n-1}\equiv 1\text{ (mod }p) \end{equation*}

for all primes $p$ dividing $F_n\text{.}$ Now, what order does $3$ have here?

Since $F_n-1=2^{2^n}\text{,}$ that means 3 has order some power of $2$ (in $U_p$).
But 3 can't have order $2^{2^n-1}$ (or less), because it isn't the identity when taken to that power.
So it must have order $2^{2^n}\text{.}$

The only way 3 can have that big an order is if $p$ is at least $2^{2^n}+1=F_n\text{.}$ So since $p\mid F_n\text{,}$ they must be equal!

🔗

Remark 17.5.2.

Interestingly, Mersenne numbers can sometimes also be shown to be composite using quadratic residues. For instance, $2^p-1$ with exponent $p\equiv 3\text{ (mod 4})$ which is itself a Germain prime must be composite. See [C.2.13, Theorem 7.6], and see [C.2.4, Exercises 9.1.37-40] for many more criteria like this.

🔗

Subsection 17.5.3 Yes, even cryptography

🔗

Suppose we have two primes

$p$ and

$q$ that are both of the form

$4n+3\text{.}$ Then it should (probabilistically) be possible to find a number

$a$ such that

$\begin{equation*} \left(\frac{a}{p}\right)=-1=\left(\frac{a}{q}\right)\text{ so that }\left(\frac{a}{pq}\right)=1 \end{equation*}$

🔗

where the latter symbol is a Jacobi symbol (recall Definition 17.4.8).

🔗

Then the Goldwasser-Micali cryptosystem uses the fact that it isn't obvious whether a Jacobi symbol which equals one implies

$a$ is actually a quadratic residue to create a public-key cryptosystem.

🔗

Now, does this really use quadratic reciprocity? It's true that decryption is possible using criteria like Euler's if you have the factorization

$n=pq\text{,}$ and the Legendre/Jacobi symbol would be multiplicative with or without Theorem 17.4.1. But to my mind one wouldn't have even had the thought to create such a system (or even the Jacobi symbol itself) without the full theorem, so it seems appropriate to mention this application here.

🔗

Subsection 17.5.4 Solving equations

🔗

There is even more! As one example, quadratic reciprocity (or at least the Legendre symbol) helps us solve Mordell equations; e.g. Fact 15.3.3 and similar facts implicitly use

$\left(\frac{-1}{p}\right)\text{.}$ The next easiest cases use

$\left(\frac{2}{p}\right)$ and multiplicativity. But more advanced ones need to compute more complicated square roots. Here are two examples, without proof.

The equation $x^3=y^2+16$ has no integer solutions. (Uses $\left(\frac{-8}{p}\right)\text{.}$ )
The equation $x^3=y^2-46$ has no integer solutions. (Uses $\left(\frac{-18}{p}\right)\text{.}$ )

🔗

There are many others solvable with the Legendre symbol. See for example [C.4.6, Theorem 9.12] or [C.2.8, Section 7.4C], the latter of which explicitly uses quadratic reciprocity.

🔗

Subsection 17.5.5 Artin's conjecture

🔗

Let's return to the test for

$F_n$ 's primality in Fact 17.5.1. A careful look at the proof shows that

$3$ is a primitive root for

$F_n\text{,}$ if

$F_n$ is prime. Thus, if we had infinitely many Fermat primes (and not just five of them), we'd have an integer which is a primitive root of infinitely many primes.

🔗

Such would provide a proof of at least one explicit case for the following long-standing question.

🔗

Conjecture 17.5.3. Artin's Conjecture.

Every nonsquare integer except $-1$ is a primitive root for infinitely many primes.

🔗

This conjecture is interesting for several reasons.

Although it is mostly believed to be true, currently there are no integers known to be a primitive root for infinitely primes.
Weirder, it is known that at least one of $3\text{,}$ $5\text{,}$ or $7$ is a primitive root for infinitely many primes) but we don't know which one!
Weirdest, it has been proved that there are at most two exceptions to this conjecture, yet we also know of no integers which do not satisfy it!

That is, there are at most two nonsquare integers which are not a primitive root for infinitely many primes, yet we do not have a single specific integer which we can prove that for.

🔗

There is some historical connection as well. Gauss spent some time investigating the patterns of repetitions in simple decimal expansions of fractions, like

$\frac{1}{3}=.333\ldots$ or

$\frac{2}{7}=.285714285714\ldots \text{.}$ It turns out that this is directly connected to whether

$10$ is a primitive root for a given prime (see Exercise 17.7.21). Likewise, when Euler found that

$F_5=4294967297$ was composite (recall Subsection 12.1.1) he would have been helped along quite a bit by information about this conjecture, as his proof looked directly at factors of powers of 2 (plus one) and their possible form, not powers of 3.

xxxxxxxxxx
 
@interact
def _(n=(1,[1..6])):
    F = 2^(2^n)+1
    a = mod(3,F)
    if a.multiplicative_order()==F-1:
        pretty_print(html("$3$ is a primitive root of $F_{%s}=%s$"%(n,F)))
    else:
        pretty_print(html("Not prime, no primitive root!"))

🔗

We can use these ideas to find another possible way to attack Artin's Conjecture. It's not directly related to reciprocity per se, but still connects all our theoretical ideas of the last several sections.

🔗

Example 17.5.4.

We put this in the form of several steps. Verifying several facts in these steps is left to Exercise Group 17.7.8–11.

Recall from the very end of Section 11.6 that if $q$ and $p=2q+1$ are both odd primes, then we call $q$ a Germain prime. In that case, every residue of $p$ other than $a=-1$ and $a=0$ is a primitive root or a QR. One way to interpret this is as complementing Fact 16.4.5, which characterizes even powers of a primitive root as being QRs; namely, for $p$ nearly all odd powers must be primitive roots.

Such a prime $p$ must be of the form $p\equiv 3\text{ (mod }4)\text{.}$ This follows because $q$ is odd so $q=2k+1$ for some integer $k\text{,}$ yielding

$\begin{equation*} p=2(2k+1)+1=4k+3\text{.} \end{equation*}$

(This is how we know that $-1\text{,}$ which is clearly not a primitive root, also isn't a QR; recall Fact 16.1.2.)

In this case, not only are all residues other than $0,-1$ either a primitive root or a QR, but $a$ is one of these things precisely when $p-a$ is the other. We know that

$\begin{equation*} 1^2,2^2,3^2,\ldots,q^2 \end{equation*}$

are all different modulo $p\text{,}$ and of course all of these are QRs (and so not primitive roots).

Here is the key; that means that the additive inverses of perfect squares, $p-k^2\text{,}$ for $2\leq k\leq q\text{,}$ must all be primitive roots. The smallest of these, $p-4\text{,}$ must thus be a primitive root for any such (safe; recall Subsection 11.6.4) prime $p=2q+1\text{.}$

🔗

So if there were infinitely many such Germain primes, we would also have an explicit example of Artin's conjecture … but, so far, no such luck.

🔗

The largest currently known (as of this writing, discovered in early 2016) Germain prime, due to James Scott Brown, is

$\begin{equation*} 2618163402417\cdot 2^{1290000} - 1 \end{equation*}$

🔗

which is a number with close to four hundred thousand digits. (The previous record had about half as many, so this is a huge advance.)

xxxxxxxxxx
 
@interact
def _(q=(11,[r for r in prime_range(3,100) if is_prime(2*r+1)])):
    p = 2*q+1
    a=mod(p-4,p)
    if a.multiplicative_order()==p-1:
        pretty_print(html("$-4$ is a primitive root of $%s$"%p))
    else:
        pretty_print(html("Mistake!"))