The quadratic reciprocity law and the supplements

Posted on February 19, 2023 by Dan Ma

The preceding two posts derive several supplements to the law of quadratic reciprocity (links are given below). We gather all the derived information in one post so that we have everything in one place.

The Law of Quadratic Reciprocity

We first state the law of quadratic reciprocity. For the main part, $p$ and $q$ are two distinct odd primes. For the first and second supplements, $p$ is an odd prime and $a$ is relatively prime to $p$ . A prior discussion on the Legendre symbol is found here.

The Main Part – the Law of Quadratic Reciprocity

$\displaystyle \biggl(\frac{q}{p}\biggr) \biggl(\frac{p}{q}\biggr)=(-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}$

$\displaystyle \biggl(\frac{q}{p}\biggr)= \left\{ \begin{array}{rl} \displaystyle \biggl(\frac{p}{q}\biggr) &\ \text{if } p \equiv 1 \ \text{mod} \ 4 \text{ or } q \equiv 1 \ \text{mod} \ 4 \\ \displaystyle - \biggl(\frac{p}{q}\biggr) &\ \text{if } p \equiv q \equiv 3 \ \text{mod} \ 4 \end{array} \right.$

The First Supplement to the Law of Quadratic Reciprocity

$\displaystyle \biggl(\frac{-1}{p}\biggr)=(-1)^{\frac{p-1}{2}} = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv 1 \ \text{mod} \ 4 \\ -1 &\ \text{if } p \equiv 3 \ \text{mod} \ 4 \end{array} \right.$

The Second Supplement to the Law of Quadratic Reciprocity

$\displaystyle \biggl(\frac{2}{p}\biggr)=(-1)^{\frac{p^2-1}{8}} = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv 1 \ \text{mod} \ 8 \text{ or } p \equiv 7 \ \text{mod} \ 8 \\ -1 &\ \text{if } p \equiv 3 \ \text{mod} \ 8 \text{ or } p \equiv 5 \ \text{mod} \ 8 \end{array} \right.$

Additional Supplements

We focus on these additional supplements:

$(\frac{-2}{p})$ , $(\frac{3}{p})$ and $(\frac{-3}{p})$ (derived here)
$(\frac{5}{p})$ , $(\frac{-5}{p})$ , $(\frac{7}{p})$ and $(\frac{-7}{p})$ (derived here)

Supplement for the Quadratic Character -2

$\displaystyle \biggl(\frac{-2}{p}\biggr)=(-1)^{\frac{p^2+4p-5}{8}} = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv 1 \ \text{mod} \ 8 \text{ or } p \equiv 3 \ \text{mod} \ 8 \\ -1 &\ \text{if } p \equiv 5 \ \text{mod} \ 8 \text{ or } p \equiv 7 \ \text{mod} \ 8 \end{array} \right.$

Supplement for the Quadratic Character 3
This works for all primes $p >3$ .

$\displaystyle \biggl(\frac{3}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv 1 \ \text{mod} \ 12 \text{ or } p \equiv 11 \ \text{mod} \ 12 \\ -1 &\ \text{if } p \equiv 5 \ \text{mod} \ 12 \text{ or } p \equiv 7 \ \text{mod} \ 12 \end{array} \right.$

$\displaystyle \biggl(\frac{3}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv \pm 1 \ \text{mod} \ 12 \\ -1 &\ \text{if } p \equiv \pm 5 \ \text{mod} \ 12 \end{array} \right.$

Supplement for the Quadratic Character -3
This works for all primes $p >3$ .

$\displaystyle \biggl(\frac{-3}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv 1 \ \text{mod} \ 3 \\ -1 &\ \text{if } p \equiv 2 \ \text{mod} \ 3 \end{array} \right.$

Supplement for Quadratic Character 5
This works for all primes $p >5$ ,

$\displaystyle \biggl(\frac{5}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv 1 \ \text{mod} \ 5 \text{ or } p \equiv 4 \ \text{mod} \ 5 \\ -1 &\ \text{if } p \equiv 2 \ \text{mod} \ 5 \text{ or } p \equiv 3 \ \text{mod} \ 5 \end{array} \right.$

$\displaystyle \biggl(\frac{5}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv \pm 1 \ \text{mod} \ 5 \\ -1 &\ \text{if } p \equiv \pm 2 \ \text{mod} \ 5 \end{array} \right.$

Supplement for Quadratic Character -5
This works for all primes $p >5$ ,

$\displaystyle \biggl(\frac{-5}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv 1,3,7,9 \ \text{mod} \ 20 \\ -1 &\ \text{if } p \equiv 11,13,17,19 \ \text{mod} \ 20 \end{array} \right.$

Supplement for Quadratic Character 7
This works for all primes $p >7$ ,

$\displaystyle \biggl(\frac{7}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv 1,3,9,19,25,27 \ \text{mod} \ 28 \\ -1 &\ \text{if } p \equiv 5,11,13,15,17,23 \ \text{mod} \ 28 \end{array} \right.$

Supplement for Quadratic Character -7
This works for all primes $p >7$ ,

$\displaystyle \biggl(\frac{-7}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv 1,2,4 \ \text{mod} \ 7 \\ -1 &\ \text{if } p \equiv 3,5,6 \ \text{mod} \ 7 \end{array} \right.$

Daniel Ma prime number

Daniel Ma quadratic residue

Daniel Ma quadratic reciprocity

Daniel Ma law of quadratic reciprocity

Dan Ma law of quadratic reciprocity

Dan Ma quadratic residue

Dan Ma prime number

$\copyright$ 2023 – Dan Ma

More extension of quadratic reciprocity

Posted on February 18, 2023 by Dan Ma

The law of quadratic reciprocity shows how to flip the Legendre symbol $(\frac{q}{p})$ to $(\frac{p}{q})$ or $-(\frac{p}{q})$ along with two supplements showing how to evaluate the Legendre symbols $(\frac{-1}{p})$ and $(\frac{2}{p})$ . The previous post gives three more supplements showing how to evaluate $(\frac{-2}{p})$ , $(\frac{3}{p})$ and $(\frac{-3}{p})$ . More supplements to the law of quadratic reciprocity are given below for $(\frac{5}{p})$ , $(\frac{-5}{p})$ , $(\frac{7}{p})$ and $(\frac{-7}{p})$ .

The exercise is not to derive more and more supplements to the law of quadratic reciprocity. That will be an endless task. The exercise demonstrated here stops at $(\frac{7}{p})$ and $(\frac{-7}{p})$ . The goal of the exercise is to demonstrate how to use the reciprocity law (the rule for flipping symbols) and the Chinese Remainder Theorem (CRT) to derive additional supplements. Thus, the goal of the exercise is about an application of the reciprocity law and an application of CRT. See here for a discussion of CRT.

Just to be clear, in the Legendre symbol $(\frac{q}{p})$ , both $p$ and $q$ are odd primes. For the symbol $(\frac{a}{p})$ , $p$ is an odd prime and $a$ is an integer that is relatively prime to $p$ . When $(\frac{a}{p})=1$ , it means that $a$ is a quadratic residue modulo $p$ , which means that the congruence equation $x^2 \equiv a \ \text{mod} \ p$ has solutions in $x$ . When $(\frac{a}{p})=-1$ , it means that $a$ is a quadratic nonresidue modulo $p$ , which means that the congruence equation $x^2 \equiv a \ \text{mod} \ p$ has no solutions in $x$ .

The Additional Supplements

Supplement for Quadratic Character 5
We show that for all primes $p >5$ ,

$\displaystyle \biggl(\frac{5}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv \pm 1 \ \text{mod} \ 5 \\ -1 &\ \text{if } p \equiv \pm 2 \ \text{mod} \ 5 \end{array} \right.$

Supplement for Quadratic Character -5
We show that for all primes $p >5$ ,

Supplement for Quadratic Character 7
We show that for all primes $p >7$ ,

Supplement for Quadratic Character -7
We show that for all primes $p >7$ ,

$\displaystyle \biggl(\frac{-7}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv 1,2,4 \ \text{mod} \ 7 \\ -1 &\ \text{if } p \equiv 3,5,6 \ \text{mod} \ 7 \end{array} \right.$

The Derivations

Supplement for Quadratic Character 5
We show that for all primes $p >5$ ,

$\displaystyle \biggl(\frac{5}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv \pm 1 \ \text{mod} \ 5 \\ -1 &\ \text{if } p \equiv \pm 2 \ \text{mod} \ 5 \end{array} \right.$

The overall idea is to flip $(\frac{5}{p})$ to $(\frac{p}{5})$ or $-(\frac{p}{5})$ using the reciprocity law. Once that is done, we can evaluate the symbol using the status of quadratic residue modulo 5. We first show that $(\frac{5}{p})=(\frac{p}{5})$ . Using the reciprocity law, note that

$(\frac{5}{p}) \times (\frac{p}{5})=(-1)^{\frac{p-1}{2} \frac{5-1}{2}}=(-1)^{p-1}=1$

Thus, the values of $(\frac{5}{p})$ depend only on the status of quadratic residue of modulo 5. We know that 1 and 4 are quadratic residues modulo 5 while 2 and 3 are quadratic nonresidues modulo 5.

Supplement for Quadratic Character -5
We show that for all primes $p >5$ ,

First, use the first supplement to express $(\frac{-5}{p})$ in terms of $(\frac{5}{p})$ .

$\displaystyle \biggl(\frac{-5}{p}\biggr)=\biggl(\frac{-1}{p}\biggr) \times \biggl(\frac{5}{p}\biggr) = \left\{ \begin{array}{rl} \displaystyle \biggl(\frac{5}{p}\biggr) &\ \text{if } p \equiv 1 \ \text{mod} \ 4 \\ \displaystyle -\biggl(\frac{5}{p}\biggr) &\ \text{if } p \equiv 3 \ \text{mod} \ 4 \end{array} \right.$

Consider the following 4 scenarios.

……..

$(\frac{-5}{p})=(\frac{5}{p})=1$

………….

$p \equiv 1 \ \text{mod} \ 4$

$p \equiv 1,4 \ \text{mod} \ 5$

……..

$(\frac{-5}{p})=(\frac{5}{p})=-1$

……….

$p \equiv 1 \ \text{mod} \ 4$

$p \equiv 2,3 \ \text{mod} \ 5$

……..

$(\frac{-5}{p})=-(\frac{5}{p})=-1$

…….

$p \equiv 3 \ \text{mod} \ 4$

$p \equiv 1,4 \ \text{mod} \ 5$

……..

$(\frac{-5}{p})=-(\frac{5}{p})=1$

……….

$p \equiv 3 \ \text{mod} \ 4$

$p \equiv 2,3 \ \text{mod} \ 5$

These 4 scenarios represent the 4 quadratic residue/nonresidue statuses modulo 5 and the two cases in $(\frac{-5}{p})$ , generating 8 systems of congruence equations.

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 1 \ \text{mod} \ 4 \\ p \equiv 1 \ \text{mod} \ 5 \end{array} \right.$

……..

…

$p \equiv 1 \ \text{mod} \ 20$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 1 \ \text{mod} \ 4 \\ p \equiv 4 \ \text{mod} \ 5 \end{array} \right.$

……..

…

$p \equiv 9 \ \text{mod} \ 20$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 1 \ \text{mod} \ 4 \\ p \equiv 2 \ \text{mod} \ 5 \end{array} \right.$

……..

…

$p \equiv 17 \ \text{mod} \ 20$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 1 \ \text{mod} \ 4 \\ p \equiv 3 \ \text{mod} \ 5 \end{array} \right.$

……..

…

$p \equiv 13 \ \text{mod} \ 20$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 3 \ \text{mod} \ 4 \\ p \equiv 1 \ \text{mod} \ 5 \end{array} \right.$

……..

…

$p \equiv 11 \ \text{mod} \ 20$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 3 \ \text{mod} \ 4 \\ p \equiv 4 \ \text{mod} \ 5 \end{array} \right.$

……..

…

$p \equiv 19 \ \text{mod} \ 20$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 3 \ \text{mod} \ 4 \\ p \equiv 2 \ \text{mod} \ 5 \end{array} \right.$

……..

…

$p \equiv 7 \ \text{mod} \ 20$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 3 \ \text{mod} \ 4 \\ p \equiv 3 \ \text{mod} \ 5 \end{array} \right.$

……..

…

$p \equiv 3 \ \text{mod} \ 20$

According to the Chinese Remainder Theorem (CRT), each system of equation has a unique solution modulo 20. Combining the solutions produces the supplement for $(\frac{-5}{p})$ stated above.

Supplement for Quadratic Character 7
We show that for all primes $p >7$ ,

First, we use the reciprocity law to flip $(\frac{7}{p})$ , with the following results.

$\displaystyle \biggl(\frac{7}{p}\biggr) = \left\{ \begin{array}{rl} \displaystyle \biggl(\frac{p}{7}\biggr) &\ \text{if } p \equiv 1 \ \text{mod} \ 4 \\ \displaystyle -\biggl(\frac{p}{7}\biggr) &\ \text{if } p \equiv 3 \ \text{mod} \ 4 \end{array} \right.$

Once flipped, the values of $(\frac{7}{p})$ depend only on the status of the quadratic residue modulo 7. The numbers 1, 2 and 4 are quadratic residue modulo 7 while the numbers 3, 5, and 6 are quadratic residue modulo 7. Consider the following 4 scenarios.

……..

$(\frac{7}{p})=1$

………….

$p \equiv 1 \ \text{mod} \ 4$

$p \equiv 1,2,4 \ \text{mod} \ 7$

……..

$(\frac{7}{p})=-1$

……….

$p \equiv 1 \ \text{mod} \ 4$

$p \equiv 3,5,6 \ \text{mod} \ 7$

……..

$(\frac{7}{p})=-1$

……….

$p \equiv 3 \ \text{mod} \ 4$

$p \equiv 1,2,4 \ \text{mod} \ 7$

……..

$(\frac{7}{p})=1$

………….

$p \equiv 3 \ \text{mod} \ 4$

$p \equiv 3,5,6 \ \text{mod} \ 7$

These 4 scenarios generate 12 systems of congruence equations, which are shown below along with the solutions.

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 1 \ \text{mod} \ 4 \\ p \equiv 1 \ \text{mod} \ 7 \end{array} \right.$

……..

…

$p \equiv 1 \ \text{mod} \ 28$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 1 \ \text{mod} \ 4 \\ p \equiv 2 \ \text{mod} \ 7 \end{array} \right.$

……..

…

$p \equiv 9 \ \text{mod} \ 28$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 1 \ \text{mod} \ 4 \\ p \equiv 4 \ \text{mod} \ 7 \end{array} \right.$

……..

…

$p \equiv 25 \ \text{mod} \ 28$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 1 \ \text{mod} \ 4 \\ p \equiv 3 \ \text{mod} \ 7 \end{array} \right.$

……..

…

$p \equiv 17 \ \text{mod} \ 28$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 1 \ \text{mod} \ 4 \\ p \equiv 5 \ \text{mod} \ 7 \end{array} \right.$

……..

…

$p \equiv 5 \ \text{mod} \ 28$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 1 \ \text{mod} \ 4 \\ p \equiv 6 \ \text{mod} \ 7 \end{array} \right.$

……..

…

$p \equiv 13 \ \text{mod} \ 28$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 3 \ \text{mod} \ 4 \\ p \equiv 1 \ \text{mod} \ 7 \end{array} \right.$

……..

…

$p \equiv 15 \ \text{mod} \ 28$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 3 \ \text{mod} \ 4 \\ p \equiv 2 \ \text{mod} \ 7 \end{array} \right.$

……..

…

$p \equiv 23 \ \text{mod} \ 28$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 3 \ \text{mod} \ 4 \\ p \equiv 4 \ \text{mod} \ 7 \end{array} \right.$

……..

…

$p \equiv 11 \ \text{mod} \ 28$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 3 \ \text{mod} \ 4 \\ p \equiv 3 \ \text{mod} \ 7 \end{array} \right.$

……..

…

$p \equiv 3 \ \text{mod} \ 28$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 3 \ \text{mod} \ 4 \\ p \equiv 5 \ \text{mod} \ 7 \end{array} \right.$

……..

…

$p \equiv 19 \ \text{mod} \ 28$

……..

$\displaystyle \left\{ \begin{array}{rr} p \equiv 3 \ \text{mod} \ 4 \\ p \equiv 6 \ \text{mod} \ 7 \end{array} \right.$

……..

…

$p \equiv 27 \ \text{mod} \ 28$

According to the Chinese Remainder Theorem (CRT), each system of equation has a unique solution modulo 28. Combining the solutions produces the supplement for $(\frac{7}{p})$ stated above.

Supplement for Quadratic Character -7
We show that for all primes $p >7$ ,

$\displaystyle \biggl(\frac{-7}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv 1,2,4 \ \text{mod} \ 7 \\ -1 &\ \text{if } p \equiv 3,5,6 \ \text{mod} \ 7 \end{array} \right.$

First, we show that $(\frac{-7}{p})=(\frac{p}{7})$ . We start with $(\frac{-7}{p})=(\frac{-1}{p}) \times (\frac{7}{p})$ . We now apply the supplement for $(\frac{-1}{p})$ and then use the reciprocity law to flip the symbol $(\frac{7}{p})$ . Suppose $p \equiv 1 \ \text{mod} \ 4$ . Then we have $(\frac{-7}{p})=(\frac{7}{p})=(\frac{p}{7})$ . Suppose $p \equiv 3 \ \text{mod} \ 4$ . Then we have $(\frac{-7}{p})=(-1)(\frac{7}{p})=(-1) (-1) (\frac{p}{7})=(\frac{p}{7})$ . This means that the values of $(\frac{-7}{p})$ depend only on the status of the quadratic residue modulo 7. As indicated earlier, the numbers 1, 2 and 4 are quadratic residue modulo 7 while the numbers 3, 5, and 6 are quadratic residue modulo 7. Hence the supplement for $(\frac{-7}{p})$ has been derived.Daniel Ma quadratic reciprocity

Daniel Ma prime number

Daniel Ma quadratic residue

Daniel Ma quadratic reciprocity

Daniel Ma law of quadratic reciprocity

Dan Ma law of quadratic reciprocity

Dan Ma quadratic residue

Dan Ma prime number

$\copyright$ 2023 – Dan Ma

Extending the law of quadratic reciprocity

Posted on January 5, 2023 by Dan Ma

This is a small effort to extend the law of quadratic reciprocity.

The Legendre Symbol

Let $p$ be an odd prime. Let $a$ be an integer that is relatively prime to $p$ . Here’s the definition of the Legendre symbol.

$\displaystyle \biggl(\frac{a}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } a \text{ is a quadratic residue modulo }p\\ -1 &\ \text{if } a \text{ is a quadratic nonresidue modulo }p \end{array} \right.$

The bottom value of the Legendre symbol is an odd prime number. The top value is a number that is relatively prime to the bottom value. The value of the symbol is either 1 or -1. If 1, the equation $x^2 \equiv a \ \text{mod} \ p$ has solutions. If -1, the equation has no solutions. If the top value $a$ happens to be not relatively prime to $p$ then the symbol is defined to be zero.

A prior discussion on the Legendre symbol is found here.

The Law of Quadratic Reciprocity

The Main Part – the Law of Quadratic Reciprocity

$\displaystyle \biggl(\frac{q}{p}\biggr) \biggl(\frac{p}{q}\biggr)=(-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}$

The First Supplement to the Law of Quadratic Reciprocity

The Second Supplement to the Law of Quadratic Reciprocity

The Problem to be Solved

Ultimately, the problem to be solved is to determine whether the equation $x^2 \equiv a \ \text{mod} \ p$ has solutions. When this equation has solutions, we say $a$ is a quadratic residue modulo $p$ . When this equation has no solutions, we say $a$ is a quadratic nonresidue modulo $p$ . The law of quadratic reciprocity are rules that can help evaluate the Legendre symbol and in the process determine whether $a$ is a quadratic residue modulo the odd prime $p$ . With information on $(\frac{-1}{p})$ , the first supplement helps evaluate $(\frac{a}{p})$ for negative $a$ . With information on $(\frac{2}{p})$ , the second supplement helps evaluate $(\frac{a}{p})$ when $a$ is even. The main part of the law helps flip the Legendre symbol to make it easier to evaluate the symbol.

If the goal is to determine whether the equation $x^2 \equiv a \ \text{mod} \ p$ has solutions when the modulus $p$ is an odd prime, there is an alternative, which is Euler’s Criterion ( see here). Based on this criterion, to check whether $a$ is a quadratic residue modulo the odd prime $p$ , we only need to perform one modular exponentiation. If $a^{\frac{p-1}{2}}$ is congruent to 1 modulo $p$ , then the equation $x^2 \equiv a \ \text{mod} \ p$ . if $a^{\frac{p-1}{2}}$ is congruent to -1, then the equation has no solutions.

Though Euler’s criterion provides an alternative to the evaluation of the Legendre symbol, the Legendre symbol does provide information not available from using Euler’s criterion. As a concrete example, consider the number 2. To check whether 2 is a quadratic residue modulo an odd prime $p$ , we need to carry out the exponentiation $2^{\frac{p-1}{2}}$ if using Euler’s criterion. With the law of quadratic reciprocity, we only need to determine which congruence classes to which $p$ belongs. For example, if $p \equiv 1 \ \text{mod} \ 8$ or $p \equiv 7 \ \text{mod} \ 8$ , then we know 2 is a quadratic residue. We can also evaluate $\frac{p^2-1}{8}$ . If it is even, then 2 is a quadratic residue and if it is odd, then 2 is a quadratic nonresidue.

The first supplement tells us whether $-1 \equiv p-1 \ \text{mod} \ p$ is a quadratic residue. if $p \equiv 1 \ \text{mod} \ 4$ ( $p-1$ is a multiple of 4), then $p-1$ is a quadratic residue. If $p \equiv 3 \ \text{mod} \ 4$ is a quadratic nonresidue.

Such information provided by the two supplements is not trivial. For example, in looking for a primitive root, if we know 2 is a quadratic residue, then we know 2 cannot be a primitive root and we would choose another number as a candidate for primitive root. If the number 2 is a quadratic nonresidue, then 2 may or may not be a primitive root and we can carry out more calculation to confirm. Similar information can be obtained for the number $-1 \equiv p-1$ . With this motivation, we should extend the law of quadratic reciprocity by having more supplements to the law.

More Supplements

We focus on the additional supplements: $(\frac{-2}{p})$ , $(\frac{3}{p})$ and $(\frac{-3}{p})$ .

Supplement for the Quadratic Character -2

Supplement for the Quadratic Character 3

This works for all $p >3$ .

$\displaystyle \biggl(\frac{3}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv \pm 1 \ \text{mod} \ 12 \\ -1 &\ \text{if } p \equiv \pm 5 \ \text{mod} \ 12 \end{array} \right.$

Supplement for the Quadratic Character -3

This works for all $p >3$ .

$\displaystyle \biggl(\frac{-3}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv 1 \ \text{mod} \ 3 \\ -1 &\ \text{if } p \equiv 2 \ \text{mod} \ 3 \end{array} \right.$

Derivation

To obtain $(\frac{-2}{p})$ , we combine the information for $(\frac{-1}{p})$ and $(\frac{2}{p})$ , For example, $\frac{p-1}{2}+\frac{p^2-1}{8}=\frac{p^2+4p-5}{8}$ . This expression is even when $p \equiv 1 \ \text{mod} \ 8$ or $p \equiv 3 \ \text{mod} \ 8$ and is odd when $p \equiv 5 \ \text{mod} \ 8$ or $p \equiv 7 \ \text{mod} \ 8$ .

For $(\frac{3}{p})$ , we verify each case. First we eliminate two cases. If $p \equiv 3 \ \text{mod} \ 12$ or $p \equiv 9 \ \text{mod} \ 12$ , then 3 would divide $p$ , which would be impossible since $p >3$ . The remaining cases are the ones listed in the supplement shown above. Consider $p \equiv 1 \ \text{mod} \ 12$ . Under this case, we have $p \equiv 1 \ \text{mod} \ 4$ and $p \equiv 1 \ \text{mod} \ 3$ . The two conditions imply that $(\frac{3}{p})=(\frac{p}{3})=(\frac{1}{3})=1$ .

Consider $p \equiv 11 \ \text{mod} \ 12$ . Under this case, we have $p \equiv 3 \ \text{mod} \ 4$ and $p \equiv 2 \ \text{mod} \ 3$ . The two conditions imply that $(\frac{3}{p})=-(\frac{p}{3})=-(\frac{2}{3})=-(-1)=1$ .

Consider $p \equiv 5 \ \text{mod} \ 12$ . Under this case, we have $p \equiv 1 \ \text{mod} \ 4$ and $p \equiv 2 \ \text{mod} \ 3$ . The two conditions imply that $(\frac{3}{p})=(\frac{p}{3})=(\frac{2}{3})=-1$ .

Consider $p \equiv 7 \ \text{mod} \ 12$ . Under this case, we have $p \equiv 3 \ \text{mod} \ 4$ and $p \equiv 1 \ \text{mod} \ 3$ . The two conditions imply that $(\frac{3}{p})=-(\frac{p}{3})=-(\frac{1}{3})=-1$ .

For $(\frac{-3}{p})$ , we have $(\frac{-3}{p})=(\frac{-1}{p}) \times (\frac{3}{p})$ . Note that each of the 4 cases for $(\frac{3}{p})$ implies one of the 2 cases for $(\frac{-1}{p})$ . For example,

$p \equiv 1 \ \text{mod} \ 12$

$p \equiv 1 \ \text{mod} \ 4$

$p \equiv 11 \ \text{mod} \ 12$

$p \equiv 3 \ \text{mod} \ 4$

$p \equiv 5 \ \text{mod} \ 12$

$p \equiv 1 \ \text{mod} \ 4$

$p \equiv 7 \ \text{mod} \ 12$

$p \equiv 3 \ \text{mod} \ 4$

As a result, these 4 cases lead to the following rule.

$\displaystyle \biggl(\frac{-3}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv 1 \ \text{mod} \ 12 \text{ or } p \equiv 7 \ \text{mod} \ 12 \\ -1 &\ \text{if } p \equiv 5 \ \text{mod} \ 3 \text{ or } p \equiv 11 \ \text{mod} \ 12 \end{array} \right.$

Furthermore, $p \equiv 1 \ \text{mod} \ 12$ and $p \equiv 7 \ \text{mod} \ 12$ lead to $p \equiv 1 \ \text{mod} \ 3$ and $p \equiv 5 \ \text{mod} \ 12$ and $p \equiv 11 \ \text{mod} \ 12$ lead to $p \equiv 2 \ \text{mod} \ 3$ . Thus, we have the supplement as stated above.

One Application

Let $p$ be an odd prime. We know that if $a$ is a primitive root modulo $p$ , $a$ is a quadratic nonresidue, i.e. $(\frac{a}{p})=-1$ . Thus, if we know $(\frac{a}{p})=1$ , we know $a$ cannot be a primitive root modulo $p$ . With the supplements to the law of quadratic reciprocity, we can eliminate quite a few possibilities during the primitive root search.

We consider the class of Sophie Germain primes. A prime number $q$ is called a Sophie Germain prime if $p=2 \cdot q+1$ is also a prime number. Such primes $q$ are named in honor of the French mathematician Sophie Germain (1776-1831). Whenever $a$ is a Sophie Germain prime, $p=2 \cdot q+1$ is called a safe prime. For a safe prime $p$ , $p-1$ has only two prime factors, namely 2 and the Sophie Germain prime $q$ . As a result, the process of checking whether a number $a$ is a primitive root modulo a safe prime $p$ is greatly simplified. We only need to compute one exponentiation, assuming we know $p=2 \cdot q+1$ is a safe prime. If $a^q$ is congruent to -1 modulo $a$ , then $a$ is a primitive root. The theorem found here can help organize the primitive root search.

If we know $p=2 \cdot q+1$ is a safe prime greater than 7, the number 3 is always a quadratic residue modulo $p$ , i.e., $(\frac{3}{p})$ is always 1. To see this, we show that for the safe prime $p=2 \cdot q+1$ , $p \equiv 11 \ \text{mod} \ 12$ . As a result, $(\frac{3}{p})$ is always 1 for a safe prime $p$ .

First, for any prime $q$ greater than 3, $q \equiv \pm 1 \ \text{mod} \ 6$ . Note that $q \equiv 2,4 \ \text{mod} \ 6$ would mean $q$ is even and that $q \equiv 3 \ \text{mod} \ 6$ would mean $q$ is divisible by 3. Thus $q \equiv 1 \ \text{mod} \ 6$ or $q \equiv 5 \ \text{mod} \ 6$ .

For a Sophie Germain prime greater than 3, we cannot have $q \equiv 1 \ \text{mod} \ 6$ . If we have that, it would mean $p=2 \cdot q+1$ is divisible by 3, which is not possible. Thus it must that $q \equiv 5 \ \text{mod} \ 6$ . As a result, $p=2 \cdot q +1 \equiv 11 \ \text{mod} \ 12$ . According to the supplement for the quadratic character 3, we have $(\frac{3}{p})=1$ whenever $p$ is a safe prime greater than 7.

Thus, 3 can never be a primitive root modulo a safe prime $p$ . We not only can eliminate 3, we can also eliminate many multiples of 3. For example, $a=2^k \cdot 3$ is always a quadratic residue modulo a safe prime whenever the exponent $k$ is even. This is because $(\frac{a}{p})=(\frac{2}{p})^k \cdot (\frac{3}{p})$ is always 1 when $k$ is even. If 2 is also a quadratic residue modulo the safe prime $p$ , $a=2^k \cdot 3$ can never be a primitive root for any exponent $k$ .

Consider the safe prime $p$ = 4007 where the matching Sophie prime is 2003. Since $p \equiv 7 \ \text{mod} \ 8$ , $(\frac{2}{p})=1$ . We already know 3 cannot be a primitive root. Thus, any $a=2^k \cdot 3^j$ cannot be a primitive root modulo 4007 for any exponents $k$ and $j$ .

Daniel Ma quadratic reciprocity

Daniel Ma Sophie Prime

Daniel Ma Safe Prime

Daniel Ma primitive root

Dan Ma primitive root

Dan Ma quadratic reciprocity

Dan Ma Sophie Prime

Dan Ma Safe Prime

$\copyright$ 2023 – Dan Ma

A theorem to help find primitive roots

Posted on December 28, 2022 by Dan Ma

If the modulus $n$ is small and if primitive roots modulo $n$ exist, finding primitive roots can be a simple matter. In such cases, we can simply try out all possible candidate primitive roots. For large $n$ , there is no easy or simple algorithm for finding primitive roots. In this post, we present a theorem that characterizes primitive roots. If the modulus $n$ is such that $n-1$ can be factored completely, this theorem can serve as an algorithm for finding primitive roots. If the modulus $n$ is a large number, $n-1$ may be hard to factor completely and the theorem is likely not an efficient algorithm. However, the theorem will still shed some light on the task of finding a primitive root. The discussion found here contains ideas not found in the previous discussion on finding primitive roots (here and here).

Defining Primitive Roots

In the discussion that follows, $n$ is a positive integer that is used as the modulus in the modular arithmetic, which can be prime or composite. Furthermore, $a$ is a positive integer that is relatively prime to $n$ ( $a$ is coprime to $n$ ), meaning that other than the number 1, there is no divisor in common between $a$ and $n$ .

Let $\Phi(n)$ denote the Euler phi function, which represents the number of positive integers not exceeding $n$ that are relatively prime to $n$ . For example, $\Phi(6)=2$ as the only numbers under 6 that are relatively prime to 6 are 1 and 5. On the other hand, $\Phi(7)=6$ since all 6 positive numbers under 7 are relatively prime to 7. If general, if $n$ is prime, $\Phi(n)=n-1$ .

According Euler’s Theorem (see Theorem 3 here), $g^{\Phi(n)} \equiv 1 \ (\text{mod } n)$ for any $g$ that is relatively prime to the modulus $n$ . Suppose that $1 \le g \le n-1$ . The number $g$ is a primitive root modulo $n$ if $g^{t} \not \equiv 1 \ (\text{mod } n)$ for all positive $t< \Phi(n)$ . In other words, $g$ is a primitive root modulo $n$ if the least number $k$ such that $g^{k} \equiv 1 \ (\text{mod } n)$ is $\Phi(n)$ . The least such $k$ is called the order of $g$ modulo $n$ . Stated differently, $g$ is a primitive root modulo $n$ if the order of $g$ modulo $n$ is $\Phi(n)$ .

The notion of primitive root is characterized by the property that taking powers of $g$ generates all the positive integers not exceeding $n$ that are relatively prime to $n$ . More specifically, the number $g$ is a primitive root modulo $n$ if and only if the set $\{ g^1,g^2,\cdots,g^{\Phi(n)} \}$ is a complete listing of all positive integers not exceeding $n$ that are relatively prime to $n$ . Note that each power of $g$ is modulo $n$ . For a proof of this fact, see Theorem 5 here.

To give a broader context, the set $\mathbb{Z}_n= \{ 0,1,2,3,\cdots,n-1 \}$ with the modulo $n$ arithmetic is called the ring of integers modulo $n$ . When the modulus $n$ is a prime number, $\mathbb{Z}_n$ with the modulo $n$ arithmetic is called a field, which is a commutative ring in which every non-zero element has a multiplicative inverse. The field $\mathbb{Z}_n$ is a finite field. Let $\mathbb{Z}_n^*= \{ 1,2,3,\cdots,n-1 \}$ , which is called the group of units modulo $n$ . Thus every element in $\mathbb{Z}_n^*$ has a multiplicative inverse when $n$ is a prime. When $g$ is a primitive root modulo the prime $n$ , $g$ , through powering, generates all the elements of $\mathbb{Z}_n^*$ , i.e., $\mathbb{Z}_n^*=\{ g^1,g^2,\cdots,g^{n-1} \}$ . Finite fields are of fundamental importance in cryptography as well as in mathematics.

One modern application of primitive roots is the notion of discrete logarithm as used in several algorithms in public-key cryptography such as Diffie-Hellman key exchange. Let $g$ be a primitive root modulo $n$ . Let $a$ be a positive integer that is relatively prime to the modulus $n$ . According to the property stated in the preceding paragraph, there is some positive integer $h$ not exceeding $n$ such that $a \equiv g^{h} \ (\text{mod } n)$ . Such a value $h$ is called the discrete logarithm of $a$ to the base $g$ modulo $n$ , denoted by $\log_g(a)$ , with the modulus omitted. Discrete logarithms can be quickly computed in some special cases or when the modulus $n$ is small. However, there is no efficient method for identifying $h=\log_g(a)$ when $n$ is large. The security of the algorithms that rely on discrete logarithm rests on the difficulty of finding $h=\log_g(a)$ when the modulus $n$ is a large prime.

More on Primitive Roots

Before finding primitive roots, it makes sense to know if primitive roots exist for the modulus in question. In general, primitive roots only exist for a limited set of moduli. According to the primitive root theorem, primitive roots exist only for the moduli 2 and 4 and the moduli that are powers of odd primes and those that are twice the powers of odd primes. For example, when the modulus is the product of two distinct prime numbers, there exist no primitive roots. Thus there are no primitive roots for the modulus 15. When the modulus $n$ is a prime number, primitive roots exist. Primitive roots can exist for a composite modulus $n$ , but only if it is 4 or a power of an odd prime or twice the power of an odd prime. The proof of the primitive root theorem can be found here.

For a modulus $n$ that is a prime number, one thing to keep in mind is that all primitive roots are also quadratic nonresidues. Thus, it makes sense to start the primitive root search with a quadratic nonresidue. If the candidate primitive root $a$ is a quadratic residue, find another $a$ . If $a$ is a quadratic nonresidue, then it may or may not be a primitive root and further calculation should be done to confirm.

For a prime modulus $n$ , the order of a primitive root is $\Phi(n)=n-1$ . Recall that $a$ is a quadratic residue modulo $n$ means that the quadratic congruence equation $x^2 \equiv a \ (\text{mod } n)$ has solutions in $x$ . If the equation has no solutions, then $a$ is a quadratic nonresidue modulo $n$ . According to Euler’s criterion (see here), for odd prime moduli, a modular exponentiation can determine the quadratic residue or nonresidue status. If $a^{\frac{n-1}{2}} \equiv 1 \ (\text{mod } n)$ , $a$ is a quadratic residue modulo $n$ . If $a^{\frac{n-1}{2}} \equiv -1 \ (\text{mod } n)$ , $a$ is a quadratic nonresidue modulo $n$ . Note that for an odd prime modulus $n$ , if $a^{\frac{n-1}{2}} \equiv 1 \ (\text{mod } n)$ , then the order of $a$ is less than $n-1$ , which means that $a$ is not a primitive root modulo $n$ . Thus, if $a$ is a primitive root modulo the odd prime $n$ , it must be the case that $a^{\frac{n-1}{2}} \equiv -1 \ (\text{mod } n)$ . The converse of this statement is not true. See Example 3 below for a counterexample.

The Search for Primitive Roots

Suppose $g$ is a candidate primitive root for the odd prime modulus $n$ . By definition, $g$ is a primitive root if $g^t$ is not congruent to 1 for all $t< \Phi(n)=n-1$ . If $n$ is a large prime, the amount of checking would be prohibitively large. As the following theorem indicates, the number of checks can be greatly reduced.

Theorem 1
Let $g$ be relatively prime to the modulus $n$ that is an odd prime. Then $g$ is a primitive root modulo $n$ if and only if the following two conditions hold.

$g^{n-1} \equiv 1 \ (\text{mod } n)$ .
$g^{\frac{n-1}{p}} \not \equiv 1 \ (\text{mod } n)$ for each prime factor of $n-1$ .

The theorem does limit the search considerably. The number of the modular exponentiations to perform is no longer $n-1$ but is the number of prime factors of $n-1$ . This means that we need to factor $n-1$ completely. Thus, this algorithm is practical only when the prime factors of $n-1$ are small or when the prime $n$ is of a special form. To see how Theorem 1 can be applied, consider the following example.

Example 1
Consider $n$ = 6329 (a prime). Find the first 2 primitive roots modulo 6329.

Note that $n-1=2^3 \times 7 \times 113$ . The 3 prime factors are 2, 7 and 113. Then the three values for $\frac{n-1}{p}$ are $2^2 \times 7 \times 113=3164$ , $2^3 \times 113=904$ and $2^3 \times 7=56$ .

The first candidate is $a$ = 2. According to Theorem 1, we need to calculate $2^{56}$ , $2^{904}$ and $2^{3164}$ modulo 6329. The results are 5674, 2919, 1. The last term $2^{3164}$ is a 1. This clearly shows that 2 is not a primitive root modulo 6329. With $2^{3164}$ being 1, the number 2 is a quadratic residue modulo 6329, which also indicates that 2 is not a primitive root.

Now $a$ = 3. The three calculations are $3^{56}$ , $3^{904}$ and $3^{3164}$ modulo 6329 with the results being 2177, 2578, 6328. All three are not congruent to 1. Thus 3 is a primitive root modulo 6329 according to Theorem 1. Note that the last value of 6328 is congruent to -1 modulo 6329. Thus, 3 is a quadratic nonresidue modulo 6329.

Now $a$ = 5. The three calculations are $5^{56}$ , $5^{904}$ and $5^{3164}$ modulo 6329 with the results being 6211, 1, 1. With 2 of the calculations being a 1, 5 is not a primitive root modulo 6329.

The next smallest primitive root modulo 6329 is 12, supported by the calculation $12^{3164} \equiv -1 \not \equiv 1$ , $12^{904} \equiv 2919 \not \equiv 1$ and $12^{56} \equiv 4239 \not \equiv 1$ modulo 6329. $\square$

The idea in Theorem 1 can also work for composite moduli $n$ for which primitive roots exist. We only need to replace $n-1$ with $\Phi(n)$

Theorem 2
Let $g$ be relatively prime to the modulus $n$ . Then $g$ is a primitive root modulo $n$ if and only if the following two conditions hold.

$g^{\Phi(n)} \equiv 1 \ (\text{mod } n)$ .
$g^{\frac{\Phi(n)}{p}} \not \equiv 1 \ (\text{mod } n)$ for each prime factor of $\Phi(n)$ .

The proof of Theorem 1 is found in the proof section below.

More Examples

Example 2
In this example, we expand upon Example 1. Once a primitive root is found, other primitive roots can be derived from it. In this example, all primitive roots modulo 6329 can be obtained by taking $3^k$ over all values of $k$ is relatively prime to $\Phi(n)$ = 6328 (see Theorem 6 here). With $n$ = 6329, we have $\Phi(n-1)$ = 2688. Thus, for the prime modulus 6329, there exist 2688 many primitive roots. Two examples: $3^5 \equiv 243$ is a primitive root modulo 6329 as is $3^{11} \equiv 6264$ since 5 and 11 are relatively prime to 6328. On the other hand, $3^{21} \equiv 3518$ is not a primitive root modulo 6329 since 21 is not relatively prime to 6328. Note that for even $k$ , $3^k$ is not primitive root for sure since $n-1$ = 6328 is even. On the other hand, for odd $k$ , $3^k$ is a primitive root only if $k$ and $\Phi(n)=n-1$ = 6328 are relatively prime, meaning that $k$ does not have 7 and 113 as prime factors.

Recall that a primitive root through powering can generate all positive numbers not exceeding the prime modulus $n$ that are relatively prime to $n$ . In this case $3^1,3^2,\cdots,3^{6328}$ is a complete listing of the integers $1,2,3,\cdots,6328$ . Thus, any number less than the modulus should be a power of 3. For example, let’s look at 5 and 12. We see that $3^{5432} \equiv 5$ and $3^{5949} \equiv 12$ modulo 6329. Note that 5 is not a primitive root and 12 is a primitive root as shown in Example 1. Thus, the discrete logarithm of 5 base 3 is 5432 and the discrete logarithm of 12 base 3 is 5949. $\square$

Example 3
This example shows that, though primitive roots are quadratic nonresidues, quadratic nonresidues are not necessarily primitive roots. Consider $n$ = 29 with $n-1=2^2 \times 7$ . Here’s the breakdown of the primitive roots and non-primitive roots modulo 29.

Primitive roots: 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27
Non-primitive roots: 4, 5, 6, 7, 9, 12, 13, 16, 17, 20, 22, 23, 24, 25, 28

All the primitive roots are quadratic nonresidues. There are 12 primitive roots and there are 14 quadratic nonresidues in this example. There are 2 non-primitive roots that are quadratic nonresidues, namely 12 and 17. Note that $\frac{n-1}{2}=14$ . Using Euler’s criterion, $12^{14} \equiv -1 \ (\text{mod } 29)$ and $17^{14} \equiv -1 \ (\text{mod } 29)$ . Thus, 12 and 17 are quadratic nonresidues modulo 29. The reason they are not primitive roots is that $12^{4} \equiv 1 \ (\text{mod } 29)$ and $17^{4} \equiv 1 \ (\text{mod } 29)$ . In general, it is possible that $a^{\frac{n-1}{2}} \equiv -1 \ (\text{mod } n)$ but $a^{\frac{n-1}{p}} \equiv 1 \ (\text{mod } n)$ for other prime factor $p$ of $n-1$ . $\square$

Example 4
Find the first primitive root modulo the prime 97. Once the first primitive root is obtained, use it to derive another primitive root and a non-primitive root.

We apply the concept in Theorem 1. With $n$ = 97, $n-1=2^5 \times 3$ . Note that $\frac{n-1}{2}=48$ and $\frac{n-1}{3}=32$ . According to Theorem 1, compute $a^{32}$ and $a^{48}$ modulo 97 starting with $a$ = 2.

For $2^{48},3^{48},4^{48},5^{48}$ , the results are 1, 1, 1, -1 modulo 97. This shows that 2, 3, and 4 are not primitive roots modulo 97. Compute $5^{32}$ , which is 35, not congruent to 1 modulo 97. According to Theorem 1, 5 is a primitive root modulo 97.

Another primitive root is $5^{11} \equiv 71$ modulo 97 since 11 is not a prime factor of $n-1$ = 98. A non-primitive root is $5^{21} \equiv 77$ modulo 97 sine 21 is not relatively prime to 98. $\square$

Example 5
Find the first primitive root modulo the prime 986113.

We find the first quadratic nonresidue and then confirm whether that is a primitive root. If not we find the next quadratic nonresidue and so on. Note that $n-1=2^{10} \times 3^2 \times 107$ . According to Theorem 1, the relevant exponents are $\frac{n-1}{2}=493056$ , $\frac{n-1}{3}=328704$ and $\frac{n-1}{107}=9216$ . We find the first quadratic nonresidue by evaluating $a^{493056}$ starting with $a$ = 2. The calculation shows that $a^{493056} \equiv 1$ for $a$ = 2, 3 and 4. However, $5^{493056}$ is congruent to -1 modulo 986113.

We then evaluate $5^{328704}$ and $5^{9216}$ with the results 240267 and 660749, both not congruent to 1. By Theorem 1, the number 5 is a primitive root modulo 986113. $\square$

Example 6
We now consider a class of prime numbers for which Theorem 1 is an effective approach of primitive root search. A prime number $q$ is called a Sophie Germain prime if $p=2 \times q+1$ is also a prime number. Thus, the definition of Germain prime refers to a pair of prime numbers where the second term in the pair is twice the first term plus one. The first term is called a Sophie Germain prime in honor the French mathematician Sophie Germain (1776-1831) and the second term is called a safe prime. For a safe prime $p$ , the factorization of $p-1$ is completely known, which is $p-1=2 \times q$ . To check whether the primitive root candidate $a$ is a primitive root modulo the safe prime $p=2 \times q+1$ , we only need to check two exponentiations – $a^2$ and $a^q$ modulo $p$ . If both are not congruent to 1, then $a$ is a primitive root modulo $p$ . In fact, we only need to check $a^q$ . Because $p$ is a prime number, there are no non-trivial square roots of 1 modulo $p$ .

Based on the preceding paragraph, we know this fact about a safe prime $p$ where $q$ is the corresponding Sophie Germain prime with $p=2 \cdot q+1$ . With the exception of $a \equiv -1 \equiv p-1$ modulo $p$ , if $a$ is a quadratic residue modulo $p$ , then it is a primitive root modulo $p$ . This gives a clear algorithm for finding a primitive root modulo a safe prime $p$ . To determine whether $a$ is a primitive root modulo $p$ , check whether $a$ is a quadratic residue modulo $p$ . If it is, then it is not a primitive root. It $a$ is a quadratic residue modulo $p$ , then it is a primitive root. We can apply the Euler criterion to check for quadratic residue by raising $a$ to the power of the Sophie Germain prime $q$ modulo $p$ .

An example of a Sophie Germain prime is $q$ = 1,889 with the associated safe prime $p$ = 3,779. Note that $a^{1889} \equiv -1 \ \text{mod} \ 3779$ . This shows that 2 is a primitive root modulo 3,779.

For a larger example, let $q$ = 581,485,876,661, a Sophie Germain prime. The associated safe prime is $p$ = 1,162,971,753,323. To see whether 2 is a primitive root modulo $p$ , compute $2^q$ modulo $p$ , which is -1. Thus 2 is a primitive root modulo $p$ . $\square$

The Proof of Theorem 1

We prove Theorem 1. The proof for Theorem 2 is essentially the same with $n-1$ replaced by $\Phi(n)$ .

One direction is clear from definition. If $g$ is a primitive root modulo $n$ , then $g^{n-1} \equiv 1 \ (\text{mod } n)$ and $g^t$ is not 1 for any $t$ smaller than $n-1$ .

To prove the other direction, let $g$ be relatively prime to $n$ . Let $n-1=p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k}$ where $p_1,p_2,\cdots,p_k$ are the prime factors of $n-1$ and each exponent $e_i \ge 1$ . For each $i$ , let $Q_i=\frac{n-1}{p_i}$ . The two conditions in the hypothesis in the theorem are:

$g^{n-1} \equiv 1 \ (\text{mod } n)$
$g^{Q_i} \not \equiv 1 \ (\text{mod } n)$ for all $1 \le i \le k$

Let $w$ be the order of $g$ modulo $n$ , i.e., $w$ is the smallest positive integer $x$ such that $g^{x} \equiv 1 \ (\text{mod } n)$ . We know that $w$ divides $n-1$ . On the other hand, $w$ does not divide $Q_i$ for all $i$ . If it does divide $Q_i$ , we have $g^{Q_i} \equiv 1 \ (\text{mod } n)$ , against the the second condition in the hypothesis.

Since $w$ divides $n-1$ , we can write $w=p_1^{f_1} \times p_2^{f_2} \times \cdots \times p_k^{f_k}$ where $0 \le f_i \le e_i$ for each $i$ . Consider the ratio $\frac{Q_1}{w}$ , which is not an integer since $w$ does not divide $Q_1$ .

$\displaystyle \frac{Q_1}{w}=\frac{p_1^{e_1-1} \times p_2^{e_2} \times \cdots \times p_k^{e_k}}{p_1^{f_1} \times p_2^{f_2} \times \cdots \times p_k^{f_k}}$

If $f_1 \le e_1-1$ , then $w$ would divide $Q_1$ . Thus, $e_1-1 <f_1$ . Note that $f_1 \le e_1$ . If $f_1 < e_1$ , we have $f_1 \le e_1-1$ . This implies that $f_1=e_1$ . By the same argument, we have $f_i=e_i$ for all $1 \le i \le k$ . It follows that $w=n-1$ , i.e., the order of $g$ is $n-1$ , showing that $a$ must be a primitive root modulo $n$ . $\square$

Daniel Ma primitive root

Dan Ma primitive root

$\copyright$ 2022 – Dan Ma

Finding Square Roots Modulo an Odd Composite Number

Posted on December 26, 2022 by Dan Ma

We show how to find square roots modulo an odd composite number by building upon the tools and techniques from three previous posts. The square roots obtained here are put together using the Chinese Remainder Theorem (CRT) based on the algorithms and techniques presented in the previous posts. We present examples to illustrate how it is done.

This is the fourth in four posts. The first post: square roots modulo an odd prime. The second post: square roots modulo a product of odd primes. The third post: square roots modulo a power of an odd prime.

Examples

Example 1
Find the square roots of 2,828,662 modulo $N$ = 4,084,441.

The factorization of $N$ is $43^2 \times 47^2$ . The first step is to solve the two equations $x^2 \equiv a \ \text{mod} \ 43^2$ and $x^2 \equiv a \ \text{mod} \ 47^2$ (see here for the algorithm). Note that $2828662 \equiv 1541 \ \text{mod} \ 43^2$ and $2828662 \equiv 1142 \ \text{mod} \ 47^2$ . The first step is to solve the following two equations:

$x^2 \equiv 1541 \ \text{mod} \ 43^2$

$x^2 \equiv 1142 \ \text{mod} \ 47^2$

The first equation is solved in Example 4 here. The two solutions are 1,210 and 639 modulo square of 43. The second equation is solved in Example 5 here. The two solutions are 1,670 and 539 modulo the square of 47. The four solutions (two to each equation) generate the following four systems of equations.

(1)

……..

$\displaystyle \left\{ \begin{array}{l} x \equiv 639 \ \text{mod} \ 43^2 \\ x \equiv 539 \ \text{mod} \ 47^2 \end{array} \right.$

(2)…….. $\displaystyle \left\{ \begin{array}{l} x \equiv 639 \ \text{mod} \ 43^2 \\ x \equiv 1670 \ \text{mod} \ 47^2 \end{array} \right.$

(3)…….. $\displaystyle \left\{ \begin{array}{l} x \equiv 1210 \ \text{mod} \ 43^2 \\ x \equiv 539 \ \text{mod} \ 47^2 \end{array} \right.$

(4)…….. $\displaystyle \left\{ \begin{array}{l} x \equiv 1210 \ \text{mod} \ 43^2 \\ x \equiv 1670 \ \text{mod} \ 47^2 \end{array} \right.$

We now apply the Chinese Remainder Theorem (CRT) to obtain the square roots modulo $N$ . Before we do so, we need to find the multiplicative inverse of $43^2$ modulo $47^2$ and the multiplicative inverse of $47^2$ modulo $43^2$ . This is done by applying the extended Euclidean algorithm.

$\displaystyle (43^2)^{-1} \equiv 1037 \ \text{mod} \ 47^2$

$\displaystyle (47^2)^{-1} \equiv 981 \ \text{mod} \ 43^2$

The following steps produce the four square roots of 2,828,662 modulo $N$ .

(1)…….. $\displaystyle \begin{aligned} x&\equiv 639 \times 47^2 \times 981+539 \times 43^2 \times 1037 \\& \equiv 106032 + 122034 \\&\equiv 228066 \ \text{mod} \ (43^2 \times 47^2) \end{aligned}$

(2)…….. $\displaystyle \begin{aligned} x&\equiv 639 \times 47^2 \times 981+1670 \times 43^2 \times 1037 \\& \equiv 106032 + 3962407 \\&\equiv 4068439 \ \text{mod} \ (43^2 \times 47^2) \end{aligned}$

(3)…….. $\displaystyle \begin{aligned} x&\equiv 1210 \times 47^2 \times 981+539 \times 43^2 \times 1037 \\& \equiv 3978409 + 122034 \\&\equiv 16002 \ \text{mod} \ (43^2 \times 47^2) \end{aligned}$

(4)…….. $\displaystyle \begin{aligned} x&\equiv 1210 \times 47^2 \times 981+1670 \times 43^2 \times 1037 \\& \equiv 3978409 + 3962407 \\&\equiv 3856375 \ \text{mod} \ (43^2 \times 47^2) \end{aligned}$

The four square roots of 2,828,662 modulo $N$ are 228,066, 4,068,439, 16,002 and 3,856,375. $\square$

Example 2
Find the four square roots of 106,263,092 modulo $N$ = 130,533,497.

The factorization of the modulus $N$ is $N=163^2 \times 17^3$ . Thus, the modulus is a product of two powers of odd primes. The first step is to solve the following two equations.

$x^2 \equiv 106263092 \equiv 13661 \ \text{mod} \ 163^2$

$x^2 \equiv 106263092 \equiv 4728 \ \text{mod} \ 17^3$

These two equations are solved in Example 2 and Example 3 here. For the mod $163^2$ equation, the solutions are 13,501 and 13,068. For the mod $17^3$ equation, the solutions are 4,443 and 470. These four solutions generate the following four systems of equations.

(5)

……..

$\displaystyle \left\{ \begin{array}{l} x \equiv 13068 \ \text{mod} \ 163^2 \\ x \equiv 470 \ \text{mod} \ 17^3 \end{array} \right.$

(6)…….. $\displaystyle \left\{ \begin{array}{l} x \equiv 13068 \ \text{mod} \ 163^2 \\ x \equiv 4443 \ \text{mod} \ 17^3 \end{array} \right.$

(7)…….. $\displaystyle \left\{ \begin{array}{l} x \equiv 13501 \ \text{mod} \ 163^2 \\ x \equiv 470 \ \text{mod} \ 17^3 \end{array} \right.$

(8)…….. $\displaystyle \left\{ \begin{array}{l} x \equiv 13501 \ \text{mod} \ 163^2 \\ x \equiv 4443 \ \text{mod} \ 17^3 \end{array} \right.$

We solve these systems of equations via the Chinese Remainder Theorem (CRT). Before we do so, we find the multiplicative inverse of $163^2$ modulo $17^3$ and the multiplicative inverse of $17^3$ modulo $163^2$ by applying the extended Euclidean algorithm.

$\displaystyle (17^3)^{-1} \equiv 26158 \ \text{mod} \ 163^2$

$\displaystyle (163^2)^{-1} \equiv 76 \ \text{mod} \ 17^3$

The square roots of 106,263,092 modulo $N$ are put together via CRT.

(5)…….. $\displaystyle \begin{aligned} x&\equiv 13068 \times 17^3 \times 26158+470 \times 163^2 \times 76 \\& \equiv 110832367 + 35310201 \\&\equiv 15609071 \ \text{mod} \ (163^2 \times 17^3) \end{aligned}$

(6)…….. $\displaystyle \begin{aligned} x&\equiv 13068 \times 17^3 \times 26158+4443 \times 163^2 \times 76 \\& \equiv 110832367 + 95223296 \\&\equiv 75522166 \ \text{mod} \ (163^2 \times 17^3) \end{aligned}$

(7)…….. $\displaystyle \begin{aligned} x&\equiv 13501 \times 17^3 \times 26158+470 \times 163^2 \times 76 \\& \equiv 19701130 + 35310201 \\&\equiv 55011331 \ \text{mod} \ (163^2 \times 17^3) \end{aligned}$

(8)…….. $\displaystyle \begin{aligned} x&\equiv 13501 \times 17^3 \times 26158+4443 \times 163^2 \times 76 \\& \equiv 19701130 + 95223296 \\&\equiv 114924426 \ \text{mod} \ (163^2 \times 17^3) \end{aligned}$

The four square roots of 106,263,092 modulo $N$ are 15,609,071, 75,522,166, 55,011,331, and 114,924,426. $\square$

Daniel Ma quadratic residue
Daniel Ma quadratic nonresidue
Daniel Ma finding square roots modulo an odd composite number
Dan Ma quadratic residue
Dan Ma quadratic nonresidue
Dan Ma finding square roots modulo an odd composite number

$\copyright$ 2022 – Dan Ma

Finding Square Roots Modulo a Power of an Odd Prime

Posted on December 26, 2022 by Dan Ma

This is a continuation of the discussion on finding square roots. The first case is on finding square roots modulo an odd prime (see here), which is the basis for all other cases. The second case is on finding square roots modulo a product of distinct odd primes (see here). The case discusses here is on finding square roots modulo a power of an odd prime.

This is the third in four posts. The first post: square roots modulo an odd prime. The second post: square roots modulo a product of odd primes. The fourth post: square roots modulo an odd composite number.

The discussion here focuses on finding the square roots of $a$ modulo $p^e$ where $p$ is an odd prime and $e \ge 1$ . In other words, we would like to solve the equation $x^2 \equiv a \ \text{mod} \ p^e$ . We present an algorithm attributed to Tonelli that relates the square roots modulo $p$ to the square roots modulo $p^e$ . The goal is to obtain mod $p^e$ information based on mod $p$ information.

Connecting Modulo Odd Prime to Modulo Power of Odd Prime

As indicated above, let $p$ be an odd prime and let $e \ge 1$ be an exponent. Let $a$ be an integer that is relatively prime to $p$ . We would like to find the square roots of $a$ modulo $p^e$ . To find the square roots of $a$ , the number $a$ must be a quadratic residue. There are two moduli involved – $p$ and $p^e$ . It turns out that the number $a$ is a quadratic residue modulo $p$ if and only if $a$ is a quadratic modulo $p^e$ . Thus, between these two moduli, the number $a$ has square roots in one modulus would mean that it has square roots in the other modulus.

An algorithm to connect modulo an odd prime to modulo a power of the odd prime

Let $p$ be an odd prime. Let $e \ge 1$ . If $w$ is a solution to the equation $y^2 \equiv a \ \text{mod} \ p$ , then a solution to the equation $x^2 \equiv a \ \text{mod} \ p^e$ is given by:

$\displaystyle x \equiv w^{p^{e-1}} \times a^{\frac{p^e-2p^{e-1}+1}{2}} \ \text{mod} \ p^e$

The algorithm is dated to 1891 and is attributed to A. Tonelli. We illustrate how this works in several exampls.

Examples

Example 1
Find the square roots of 15,621 modulo 26,569, which is the square of the prime number 163.

The first step is to solve the mod 163 equation $y^2 \equiv 15621 \equiv 136 \ \text{mod} \ 163$ . The solutions are given by:

$\displaystyle y \equiv \pm 136^{\frac{163+1}{2}} \equiv \pm 136^{41} \equiv \pm 25 \ \text{mod} \ 163$

Thus the mod 163 square roots are 25 and -25, which is congruent to 138 modulo 163. It is a good idea to check that 136 is a quadratic residue mod 163. To see this, note that $25^2 \equiv 136$ modulo 163. Based on the observation made earlier, this ensures that 15,621 is a quadratic residue modulo the square of 163. We then plug each of these square roots into the above algorithm

$\displaystyle \begin{aligned} x&\equiv 25^{163} \times 15621^{\frac{163^2-2 \cdot 163 + 1}{2}} \\& \equiv 16325 \times 15621^{13122} \\&\equiv 16325 \times 17768 \\&\equiv 8827 \ \text{mod} \ 26569 \end{aligned}$

$\displaystyle \begin{aligned} x&\equiv 138^{163} \times 15621^{\frac{163^2-2 \cdot 163 + 1}{2}} \\& \equiv 10244 \times 15621^{13122} \\&\equiv 10244 \times 17768 \\&\equiv 17742 \ \text{mod} \ 26569 \end{aligned}$

Thus, the two square roots of 15,621 modulo the square of 163 are 8,827 and 17,742. $\square$

Example 2
Find the square roots of 13,661 modulo 26,569, which is the square of the prime number 163.

The first step is to solve the mod 163 equation $y^2 \equiv 13661 \equiv 132 \ \text{mod} \ 163$ . The solutions are given by:

$\displaystyle y \equiv \pm 132^{\frac{163+1}{2}} \equiv \pm 132^{41} \equiv \pm 135 \ \text{mod} \ 163$

Thus the mod 163 square roots are 135 and -135, which is congruent to 28 modulo 163. It is a good idea to check that 136 is a quadratic residue mod 163. To see this, note that $135^2 \equiv 132$ modulo 163. Based on the observation made earlier, this ensures that 13,661 is a quadratic residue modulo the square of 163. We then plug each of these square roots into the above algorithm

$\displaystyle \begin{aligned} x&\equiv 135^{163} \times 13661^{\frac{163^2-2 \cdot 163 + 1}{2}} \\& \equiv 4373 \times 13661^{13122} \\&\equiv 4373 \times 26244 \\&\equiv 13501 \ \text{mod} \ 26569 \end{aligned}$

$\displaystyle \begin{aligned} x&\equiv 28^{163} \times 13661^{\frac{163^2-2 \cdot 163 + 1}{2}} \\& \equiv 22196 \times 13661^{13122} \\&\equiv 22196 \times 26244 \\&\equiv 13068 \ \text{mod} \ 26569 \end{aligned}$

Thus, the two square roots of 13,661 modulo the square of 163 are 13,501 and 13,068. $\square$

Example 3
Find the square roots of 4,728 modulo 4,913, which is the cube of the prime number 17.

The first step is to solve the mod 17 equation $y^2 \equiv 4728 \equiv 2 \ \text{mod} \ 17$ . The solutions are 6 and 11 (-6) modulo 17. The modulus is small enough so that we can obtain the square roots by squaring all the numbers below 17. We then plug each of these square roots into the above algorithm

$\displaystyle \begin{aligned} x&\equiv 6^{17^2} \times 4728^{\frac{17^3-2 \cdot 17^2 + 1}{2}} \\& \equiv 4086 \times 4728^{2168} \\&\equiv 4086 \times 1361 \\&\equiv 4443 \ \text{mod} \ 4913 \end{aligned}$

$\displaystyle \begin{aligned} x&\equiv 11^{17^2} \times 4728^{\frac{17^3-2 \cdot 17^2 + 1}{2}} \\& \equiv 827 \times 4728^{2168} \\&\equiv 827 \times 1361 \\&\equiv 470 \ \text{mod} \ 4913 \end{aligned}$

Thus, the two square roots of 4,728 modulo the cube of 17 are 4,443 and 470. $\square$

Example 4
Solve the congruence equation $x^2 \equiv 1541 \ \text{mod} \ 43^2$ .

The first step is to solve the equation $x^2 \equiv 1541 \equiv 36 \ \text{mod} \ 43$ . From the equation, it is clear that $x \equiv \pm 6 \ \text{mod} \ 43$ . Thus, the two solutions to this equations are 6 and 37 (-6) modulo 43. We use these two square roots to build the square roots for mod square of 43.

$\displaystyle \begin{aligned} x&\equiv 6^{43} \times 1541^{\frac{43^2-2 \cdot 43 + 1}{2}} \\& \equiv 1425 \times 1541^{882} \\&\equiv 1425 \times 1506 \\&\equiv 1210 \ \text{mod} \ 43^2 \end{aligned}$

$\displaystyle \begin{aligned} x&\equiv 37^{43} \times 1541^{\frac{43^2-2 \cdot 43 + 1}{2}} \\& \equiv 424 \times 1541^{882} \\&\equiv 424 \times 1506 \\&\equiv 639 \ \text{mod} \ 43^2 \end{aligned}$

Thus, the two square roots of 1541 modulo the square of 43 are 1,210 and 639. $\square$

Example 5
Solve the congruence equation $x^2 \equiv 1142 \ \text{mod} \ 47^2$ .

The first step is to solve the equation $x^2 \equiv 1541 \equiv 14 \ \text{mod} \ 47$ . Note that $47 \equiv 3 \ \text{mod} \ 4$ and that $\frac{47+1}{2}=12$ . To solve this equation, evaluate $x \equiv \pm 14^{12} \pm 25 \ \text{mod} \ 47$ . Thus, the two solutions to this equation are 25 and 22 (-25) modulo 47. We use these two square roots to build the square roots for mod square of 43.

$\displaystyle \begin{aligned} x&\equiv 25^{47} \times 1142^{\frac{47^2-2 \cdot 47 + 1}{2}} \\& \equiv 2093 \times 1142^{1058} \\&\equiv 2093 \times 1928 \\&\equiv 1670 \ \text{mod} \ 47^2 \end{aligned}$

$\displaystyle \begin{aligned} x&\equiv 22^{47} \times 1142^{\frac{47^2-2 \cdot 47 + 1}{2}} \\& \equiv 116 \times 1142^{1058} \\&\equiv 116 \times 1928 \\&\equiv 539 \ \text{mod} \ 47^2 \end{aligned}$

Thus, the two square roots of 1,142 modulo the square of 47 are 1,670 and 539. $\square$

Daniel Ma quadratic residue
Daniel Ma quadratic nonresidue
Daniel Ma finding square roots modulo power of odd prime
Dan Ma quadratic residue
Dan Ma quadratic nonresidue
Dan Ma finding square roots modulo power of odd prime

Finding Square Roots Modulo a Product of Odd Primes

Posted on December 25, 2022 by Dan Ma

In the previous post, we show how to find square roots modulo an odd prime. In this post, we show how to find square roots modulo a product of odd primes via the Chinese Remainder Theorem.

This is the second in four posts. The first post: square roots modulo an odd prime. The third post: square roots modulo a power of an odd prime. The fourth post: square roots modulo an odd composite number.

Let $n$ be a product of distinct odd prime numbers. Let $a$ be an integer that is relatively prime to $n$ . Finding a square root of $a$ modulo $n$ is to solve the congruence equation $x^2 \equiv a \ \text{mod} \ n$ . The focus in this post is on composite $n$ that is a product of distinct odd primes. For example, let $n=p \times q$ where $p$ and $q$ are distinct odd primes. To find solutions to $x^2 \equiv a \ \text{mod} \ n$ , we first find solutions to the equation modulo $p$ and the solutions to the equation modulo $q$ . Then obtain the solutions to the same equation modulo $n$ . This is done via an application of the Chinese Remainder Theorem.

The algorithm demonstrated in the examples below requires the knowledge of the prime factors of the modulus $n$ . Without the knowledge of the prime factors of the modulus $n$ , finding square roots is a difficult problem when the prime factors are large. For the case of $n=p \times q$ , when the distinct odd primes $p$ and $q$ are large and are kept secret with their product $n$ publicly known, solving the equation $x^2 \equiv a \ \text{mod} \ n$ is the basis for the security of the Rabin Cryptosystem. In this scheme, the encrypted message is $c$ (the ciphertext). The original message (the plaintext) is $m$ such that $m^2 \equiv c \ \text{mod} \ n$ . If the prime factors $p$ and $q$ of the modulus $n$ are known, then the equation becomes solvable as shown in the examples below. But if $p$ and $q$ are not known, finding the square roots of the ciphertext $c$ has been proven to be as hard as factoring the modulus $n$ .

Examples

We show two examples to demonstrate how to find square roots modulo a product of distinct odd primes.

Example 1
Let $N$ = 319,551,913. Find the square roots of 319,401,406 modulo $N$ ,

The number $N$ is the product of the odd primes $p$ = 14,947 and $q$ = 21,379. The first task is to solve the two equations $x^2 \equiv 319401406 \ \text{mod} \ p$ and $x^2 \equiv 319401406 \ \text{mod} \ q$ . Both $p$ and $q$ are congruent to 3 modulo 4. This is the simple case of the Tonelli-Shanks algorithm for finding square roots of an odd prime (see here). Solving the mod $p$ and mod $q$ equations involves the following exponentiation.

$\displaystyle \pm 319401406^{\frac{p+1}{4}} \equiv \pm 319401406^{3737} \equiv 13910^{3737} \equiv \pm 3002 \ \text{mod} \ p$

$\displaystyle -3002 \equiv p-3002 \equiv 11945 \ \text{mod} \ p$

$\displaystyle \pm 319401406^{\frac{q+1}{4}} \equiv \pm 319401406^{5345} \equiv 20525^{5345} \equiv \pm 6375 \ \text{mod} \ q$
$\displaystyle -6375 \equiv q-6375 \equiv 15004 \ \text{mod} \ q$

Thus, the 2 solutions to the mod $p$ equation are 3002 and 11945 and the two solutions to the mod $q$ equation are 6375 and 15004. These four square roots generate four systems of congruence equations as follow.

(1)

……….

$\displaystyle \left\{ \begin{array}{l} x \equiv 3002 \ \text{mod} \ p \\ x \equiv 6375 \ \text{mod} \ q \end{array} \right.$

(2)………. $\displaystyle \left\{ \begin{array}{l} x \equiv 3002 \ \text{mod} \ p \\ x \equiv 15004 \ \text{mod} \ q \end{array} \right.$

(3)………. $\displaystyle \left\{ \begin{array}{l} x \equiv 11945 \ \text{mod} \ p \\ x \equiv 6375 \ \text{mod} \ q \end{array} \right.$

(4)………. $\displaystyle \left\{ \begin{array}{l} x \equiv 11945 \ \text{mod} \ p \\ x \equiv 15004 \ \text{mod} \ q \end{array} \right.$

The Chinese Remainder Theorem (CRT) guarantees that each system has a unique solution modulo $N=p \times q$ (see here for the description of the CRT algorithm). Thus, there are four solutions to the equation $x^2 \equiv 319401406 \ \text{mod} \ N$ or there are four square roots of 319,401,406 modulo $N$ . The first step is to find the multiplicative inverse of $p$ modulo $q$ and the multiplicative inverse of $q$ modulo $p$ . This is done using the extended Euclidean algorithm. The result is:

$\displaystyle 14947^{-1} \equiv 3972 \ \text{mod} \ q$

$\displaystyle 21379^{-1} \equiv -2777 \equiv 12170 \ \text{mod} \ p$

The following steps produce the solutions to each system of equations.

(1)

……….

$\displaystyle \begin{aligned} x&\equiv 3002 \times 21379 \times 12170 +6375 \times 14947 \times 3972 \\& \equiv 213774996 \ \text{mod} \ N \end{aligned}$

(2)………. $\displaystyle \begin{aligned} x&\equiv 3002 \times 21379 \times 12170+15004 \times 14947 \times 3972 \\& \equiv 271335893 \ \text{mod} \ N \end{aligned}$

(3)………. $\displaystyle \begin{aligned} x&\equiv 11945 \times 21379 \times 12170+6375 \times 14947 \times 3972 \\& \equiv 48216020 \ \text{mod} \ N \end{aligned}$

(4)………. $\displaystyle \begin{aligned} x&\equiv 11945 \times 21379 \times 12170+15004 \times 14947 \times 3972 \\& \equiv 105776917 \ \text{mod} \ N \end{aligned}$

See here for more information on the CRT algorithm. To verify the accuracy, we can evaluate $x^2$ modulo $N$ for each of the 4 solutions to ensure that $x^2$ is indeed 319,401,406. $\square$

Example 2
Find the eight square roots of 12,977 modulo $N$ = 1,193,221.

The modulus 1,193,221 is a Carmichael number with 3 prime factors $p$ = 31, $q$ = 61, and $r$ = 631. The problem is to solve the equation $x^2 \equiv 12977 \ \text{mod} \ N$ . The first step is to solve the three equations for mod $p$ , mod $q$ and mod $r$ . There are two solutions in each of these equations, leading to 8 systems of congruence equations.

Solving $x^2 \equiv 12977 \equiv 19 \ \text{mod} \ p$ where $p$ = 31

Note that $p \equiv 3 \ \text{mod} \ 4$ . This is the easy case of the Tonelli-Shanks algorithm (see Case 1 in the previous post). The solutions are $x \equiv 9,22 \ \text{mod} \ 31$ .

Solving $x^2 \equiv 12977 \equiv 45 \ \text{mod} \ q$ where $q$ = 61

Note that $q \equiv 1 \ \text{mod} \ 4$ . This is another special case of the Tonelli-Shanks algorithm (see Case 2 in the previous post). The solutions are $x \equiv 17,44 \ \text{mod} \ 61$ .

Solving $x^2 \equiv 12977 \equiv 357 \ \text{mod} \ r$ where $r$ = 631

Note that $r \equiv 3 \ \text{mod} \ 4$ . Just like the mod $p$ equation, this is the easy case of the Tonelli-Shanks algorithm. The solutions are $x \equiv 400,231 \ \text{mod} \ 631$ .

The solutions of the three equations generate the following systems of congruence quations.

(1)

……….

$\displaystyle \left\{ \begin{array}{l} x \equiv 9 \ \text{mod} \ p \\ x \equiv 17 \ \text{mod} \ q \\ x \equiv 231 \ \text{mod} \ r \end{array} \right.$

(2)………. $\displaystyle \left\{ \begin{array}{l} x \equiv 9 \ \text{mod} \ p \\ x \equiv 17 \ \text{mod} \ q \\ x \equiv 400 \ \text{mod} \ r \end{array} \right.$

(3)………. $\displaystyle \left\{ \begin{array}{l} x \equiv 9 \ \text{mod} \ p \\ x \equiv 44 \ \text{mod} \ q \\ x \equiv 231 \ \text{mod} \ r \end{array} \right.$

(4)………. $\displaystyle \left\{ \begin{array}{l} x \equiv 9 \ \text{mod} \ p \\ x \equiv 44 \ \text{mod} \ q \\ x \equiv 400 \ \text{mod} \ r \end{array} \right.$

(5)………. $\displaystyle \left\{ \begin{array}{l} x \equiv 22 \ \text{mod} \ p \\ x \equiv 17 \ \text{mod} \ q \\ x \equiv 231 \ \text{mod} \ r \end{array} \right.$

(6)………. $\displaystyle \left\{ \begin{array}{l} x \equiv 22 \ \text{mod} \ p \\ x \equiv 17 \ \text{mod} \ q \\ x \equiv 400 \ \text{mod} \ r \end{array} \right.$

(7)………. $\displaystyle \left\{ \begin{array}{l} x \equiv 22 \ \text{mod} \ p \\ x \equiv 44 \ \text{mod} \ q \\ x \equiv 231 \ \text{mod} \ r \end{array} \right.$

(8)………. $\displaystyle \left\{ \begin{array}{l} x \equiv 22 \ \text{mod} \ p \\ x \equiv 44 \ \text{mod} \ q \\ x \equiv 400 \ \text{mod} \ r \end{array} \right.$

We now apply the Chinese Remainder Theorem (CRT) to obtain the solution to each system of equations. According to CRT, each system has a unique solution modulo $N$ , the product of $p$ , $q$ and $r$ . Before solving the 8 systems of equations, we need to find the multiplicative inverses of $n_p=61 \cdot 631$ = 38491 (without $p$ ), $n_q=31 \cdot 631$ = 19561 (without $q$ ), and $n_r=31 \cdot 61$ = 1891 (without $r$ ). Using the extended Euclidean algorithm, they are:

$\displaystyle n_q^{-1}=38491^{-1}=14 \ \text{mod} \ p$

$\displaystyle n_p^{-1}=19561^{-1}=3 \ \text{mod} \ q$

$\displaystyle n_r^{-1}=1891^{-1}=315 \ \text{mod} \ r$

We now produce the solution to each system of equations.

System (1)
$\displaystyle \begin{aligned} x&\equiv 9 \times 38491 \times 14+17 \times 19561 \times 3 + 231 \times 1891 \times 315 \\& \equiv 259572 \ \text{mod} \ N \end{aligned}$

System (2)
$\displaystyle \begin{aligned} x&\equiv 9 \times 38491 \times 14+17 \times 19561 \times 3 + 400 \times 1891 \times 315 \\& \equiv 696393 \ \text{mod} \ N \end{aligned}$

System (3)
$\displaystyle \begin{aligned} x&\equiv 9 \times 38491 \times 14+44 \times 19561 \times 3 + 231 \times 1891 \times 315 \\& \equiv 650792 \ \text{mod} \ N \end{aligned}$

System (4)
$\displaystyle \begin{aligned} x&\equiv 9 \times 38491 \times 14+44 \times 19561 \times 3 + 400 \times 1891 \times 315 \\& \equiv 1087613 \ \text{mod} \ N \end{aligned}$

System (5)
$\displaystyle \begin{aligned} x&\equiv 22 \times 38491 \times 14+17 \times 19561 \times 3 + 231 \times 1891 \times 315 \\& \equiv 105608 \ \text{mod} \ N \end{aligned}$

System (6)
$\displaystyle \begin{aligned} x&\equiv 22 \times 38491 \times 14+17 \times 19561 \times 3 + 400 \times 1891 \times 315 \\& \equiv 542429 \ \text{mod} \ N \end{aligned}$

System (7)
$\displaystyle \begin{aligned} x&\equiv 22 \times 38491 \times 14+44 \times 19561 \times 3 + 231 \times 1891 \times 315 \\& \equiv 496828 \ \text{mod} \ N \end{aligned}$

System (8)
$\displaystyle \begin{aligned} x&\equiv 22 \times 38491 \times 14+44 \times 19561 \times 3 + 400 \times 1891 \times 315 \\& \equiv 933649 \ \text{mod} \ N \end{aligned}$

Rabin Cryptosystem

The two examples illustrate the process of how to find square roots modulo $n$ , which is a product of distinct odd primes. In this process, we first find the square roots modulo the odd primes that are factors of $n$ . We then piece together these square roots to obtain the square roots modulo $n$ via the Chinese Remainder Theorem (CRT).

One application of the algorithm of finding square roots discussed here is the Rabin cryptosystem. The process of finding square roots modulo modulo a product of odd primes discussed here is precisely the decryption process in the Rabin cryptosystem. In this system, two parties Alice and Bob wish to exchange sensitive information over an insecure communication channel. In this scheme, Bob’s secret key is a pair of large prime numbers $p$ and $q$ . Bob’s public key is the number $N$ , which is the product of $p$ and $q$ . The prime numbers $p$ and $q$ are kept secret, only known to Bob while $N$ is made public. Alice converts her plaintext into an integer $m$ between 1 and $N$ . She encrypts $m$ by making the following calculation:

$\displaystyle c \equiv m^2 \ \text{mod} \ N$

The integer $c$ is Alice’s ciphertext, which is sent to Bob. To recover the message, Bob needs to solve the congruence equation $x^2 \equiv c \ \text{mod} \ N$ . This is easy for Bob to do since he knows the prime factors $p$ and $q$ of the modulus $N$ . Eve, the eavesdropper, may intercept the ciphertext $c$ . However, unless she knows how to factor $N$ , she presumably will have a hard time trying to solve the equation $x^2 \equiv c \ \text{mod} \ N$ . In fact, solving this congruence equation is mathematically proven to be as hard as factoring integers.

Thus, the decryption is illustrated in Example 1 above. In Example 1, $N$ = 319,551,913 is Bob’s public key. His private key consists of the prime numbers $p$ = 14,047 and $q$ = 21,379. The ciphertext sent from Alice to Bob is $c$ = 319,401,406. With his knowledge of the private key, Bob can proceed to find the square roots of $c$ in the manner illustrated in Example 1.

Of course, the $p$ and $q$ in Example 1 are too small to be secure. Example 1 is only an illustration. It would be easy for Eve to factor the modulus $N$ . Secure implementations use moduli $N$ with hundreds of digits.

Note that in Example 1, there are four solutions to the equations $x^2 \equiv c \ \text{mod} \ N$ where $c$ = 319,401,406. Thus, the decryption process produces three additional messages in addition to the correct one. This is the major disadvantage of the Rabin cryptosystem. As a result, on a practical level, the Rabin cryptosystem had not been in use widely. It is possible to perform extra work to remove the ambiguity of having multiple square roots in the encryption process, for example, by choosing plaintexts with special structures or to add padding.

Daniel Ma quadratic residue
Daniel Ma quadratic nonresidue
Daniel Ma finding square roots modulo odd prime
Dan Ma quadratic residue
Dan Ma quadratic nonresidue
Dan Ma finding square roots modulo odd prime

Finding square roots modulo an odd prime

Posted on December 11, 2022 by Dan Ma

Let $p$ be an odd prime number. Let $a$ be a positive integer that is relatively prime to $p$ . We focus on two natural questions. Is $a$ a square modulo $p$ ? If it is, what are the square roots of $a$ modulo $p$ ? We answer both questions with emphasis on the second question of finding square roots.

This is the first in four posts. The second post: square roots modulo a product of odd primes. The third post: square roots modulo a power of an odd prime. The fourth post: square roots modulo an odd composite number.

In the following discussion, the modulus $p$ is an odd prime and the number $a$ is relatively prime to $p$ . Consider the quadratic congruence equation $x^2 \equiv a \ \text{mod} \ p$ . If this equation has solutions, then we say that the number $a$ is a quadratic residue modulo $p$ . If the equation has no solutions, we say that the number $a$ is a quadratic nonresidue modulo $p$ . If $a$ is a quadratic residue modulo $p$ , we also say that the number $a$ is a square modulo $p$ . A solution to the equation is called a square root of $a$ modulo $p$ . For example, for $p$ = 11, the squares are 1, 3, 4, 5, and 9. There are two square roots of 5, namely 4 and 7. Note that $4^2 \equiv 5 \ \text{mod} \ 11$ and $7^2 \equiv 5 \ \text{mod} \ 11$ .

The discussion here is on moduli that are odd prime numbers. The work on odd prime moduli can be extended to moduli that are a product of odd primes, a power of odd primes and a product of powers of odd primes. Once we know how to find square roots modulo an odd prime, we can find the squares roots modulo a product of odd primes. If the modulus $n$ is a product of distinct odd primes, then we can compute the square roots of each odd prime factor of $n$ and then obtain the square roots modulo $n$ via the Chinese Remainder Theorem. There is also an algorithm to relate the square roots modulo an odd prime to the square roots modulo a power of the same odd prime. Via the Chinese Remainder Theorem, we can relate the square roots modulo a power of odd primes to the square roots modulo a product of powers of odd primes. These ideas will be presented in the next posts.

Identifying Squares

When the modulus $p$ is small, we can identify the squares by squaring the numbers in $\{ 1,2,3,\cdots,p-1 \}$ . When $p$ is large, we have two efficient algorithms for identifying squares (quadratic residues). The first one is to use the law of quadratic reciprocity via the evaluation of the Legendre symbol (see here and here).

The other way is to use Euler’s Criterion, which states that the number $a$ is a square modulo $p$ if and only $a^{\frac{p-1}{2}} \equiv 1 \ \text{mod} \ p$ . Using Euler’s Criterion, we can determine whether $a$ is a square or a quadratic residue by performing a modular exponentiation, which can be done using the square-and-multiply algorithm (see here).

Finding Square Roots

Finding square roots is to solve the quadratic congruence equation $x^2 \equiv a \ \text{mod} \ p$ (solving for $x$ ). One approach is to use the Tonelli-Shanks algorithm. We call out two easy special cases of the algorithm. For more information on using the Tonelli-Shanks algorithm, see here. Here’s the two special cases.

Case 1: $p \equiv 3 \ \text{mod} \ 4$ .
Case 2: $p \equiv 1 \ \text{mod} \ 4$ and $p \equiv 5 \ \text{mod} \ 8$ .

Case 1 is the simplest case, which involves one modular exponentiation. Case 2 is slightly more involved, which possibly involves a second modular exponentiation.

Case 1
Let $p$ be an odd prime such that $p \equiv 3 \ \text{mod} \ 4$ . Let $a$ be a square modulo $p$ . Then the square roots of $a$ , i.e., the solutions to the congruence equation $x^2 \equiv a \ \text{mod} \ p$ , are:

……………….

$\displaystyle x \equiv \pm a^{\frac{p+1}{4}} \ \text{mod} \ p$

Case 2
Let $p$ be an odd prime such that $p \equiv 1 \ \text{mod} \ 4$ and $p \equiv 5 \ \text{mod} \ 8$ . Let $a$ be a square modulo $p$ . Then the initial estimates of the square roots of $a$ are (2a). If (2a) are not the square roots, then the square roots of $a$ are (2b).

……………….

$\displaystyle x \equiv \pm a^{\frac{p+3}{8}} \ \text{mod} \ p$

(2b)………………. $\displaystyle x \equiv \pm \biggl( a^{\frac{p+3}{8}} \cdot 2^{\frac{p-1}{4}} \biggr) \ \text{mod} \ p$

Note that Case 2 involves two sub cases. If (2a) gives the square roots, then the algorithm can stop. Otherwise perform (2b), which will be the square roots.

Examples

Example 1
Find the two square roots of 1,000 modulo the odd prime $p$ = 399,787.

Note that $p \equiv 3 \ \text{mod} \ 4$ . Thus, Case 1 is applicable. Also note that $\frac{p+1}{4}$ = 99,947. The following calculation gives the square roots of 1000.

$\displaystyle x \equiv 1000^{\frac{p+1}{4}} \equiv 1000^{99947} \equiv \pm 164301 \ \text{mod} \ p$

The two solutions are 16,301 and 235,486. Note that $-164301 \equiv 235486 \ \text{mod} \ p$ .

Example 2
Find the two square roots of 3 modulo the odd prime $p$ = 399,853.

Note that $p \equiv 1 \ \text{mod} \ 4$ and that $p \equiv 5 \ \text{mod} \ 8$ . Thus Case 2 is applicable. Furthermore, $\frac{p+3}{8}$ = 49,982. The first calculation is:

$\displaystyle x \equiv 3^{\frac{p+3}{8}} \equiv 3^{49982} \equiv \pm 154318 \ \text{mod} \ p$

Note that $154318^2 \equiv 3 \ \text{mod} \ p$ . As a result, the algorithm stops. The square roots of 3 are 154,318 and 245,535 modulo 399,853.

Example 3
Find the two square roots of 3,860 modulo the odd prime $p$ = 412,189.

Note that $p \equiv 1 \ \text{mod} \ 4$ and that $p \equiv 5 \ \text{mod} \ 8$ . Thus, Case 2 is applicable. Also note that $\frac{p+3}{8}$ = 51,524 and $\frac{p-1}{4}$ = 103,047. The first calculation is:

$\displaystyle x \equiv 3860^{\frac{p+3}{8}} \equiv 3860^{51524} \equiv \pm 328576 \ \text{mod} \ p$

Checking the calculation, we see that $328576^2 \equiv 408329 \not \equiv 3860 \ \text{mod} \ p$ . The next calculation is:

$\displaystyle \begin{aligned} x &\equiv \pm \biggl[ 2^{\frac{p-1}{4}} \cdot 3860^{\frac{p+3}{8}} \biggr]\\&\equiv \pm \biggl[ 2^{103047} \cdot 3860^{51524} \biggr] \\&\equiv \pm \biggl[ 165004 \cdot 328576 \biggr] \\&\equiv \pm 310756 \ \text{mod} \ p \end{aligned}$

To confirm the answer, note that $310756^2 \equiv 3860 \ \text{mod} \ p$ and $(-310756)^2 \equiv 101433^2 \equiv 3860 \ \text{mod} \ p$ .

Example 4
Find the two square roots of 1,893 modulo the odd prime $p$ = 412,213.

Note that $p \equiv 1 \ \text{mod} \ 4$ and that $p \equiv 5 \ \text{mod} \ 8$ . Thus, Case 2 is applicable. Also note that $\frac{p+3}{8}$ = 51,527 and $\frac{p-1}{4}$ = 103,053. The first calculation is:

$\displaystyle x \equiv 1893^{\frac{p+3}{8}} \equiv 1893^{51527} \equiv \pm 100055 \ \text{mod} \ p$

Checking the calculation, we see that $100055^2 \equiv 410320 \not \equiv 1893 \ \text{mod} \ p$ . The next calculation is:

$\displaystyle \begin{aligned} x &\equiv \pm \biggl[ 2^{\frac{p-1}{4}} \cdot 1893^{\frac{p+3}{8}} \biggr]\\&\equiv \pm \biggl[ 2^{103053} \cdot 3860^{51527} \biggr] \\&\equiv \pm \biggl[ 176571 \cdot 100055 \biggr] \\&\equiv \pm 186651 \ \text{mod} \ p \end{aligned}$

To confirm the answer, note that $186651^2 \equiv 1893 \ \text{mod} \ p$ and $(-186651)^2 \equiv 225562^2 \equiv 1893 \ \text{mod} \ p$ .

A 22-million digit prime number

Posted on January 9, 2018 by Dan Ma

The first digits of 2 to 77,232,917 minus 1

The digits in the above picture are the first digits of the newest largest prime number known to humankind. It was discovered on December 26, 2017. The number is equaled to 2 raided to 77,232,917 less 1, making this a Mersenne prime. It has over 22 million digits (23,249,425 to be precise). If we were to write 5 digits per inch, the digits would cover a stretch of highway of over 73 miles in length!

We already wrote about this newly discovered largest prime in two places (here and here).

For more on Mersenne primes, see here or Google the Internet.

$\text{ }$

Dan Ma math

Daniel Ma mathematics

Dan Ma prime numbers

Mersenne Prime

Posted on May 25, 2017 by Dan Ma

A Mersenne number is an integer that is one less than a power of 2, i.e. it is of the form $2^n-1$ where $n$ is a positive integer. A Mersenne prime number (or a Mersenne prime) is a Mersenne number that happens to be a prime number. This post is a brief discussion on Mersenne prime.

Because Mersenne numbers are exponential, they increase very rapidly. The first several Mersenne numbers $2^n-1$ starting with $n$ = 2.

127

255

511

1,023

2,047

4,095

8,191

16,383

32,767

It is clear from these examples that not all Mersenne numbers are prime (e.g. 15 and 63). In the above list, the numbers in red are prime and the ones in blue are composite. Note that the ones with composite exponent $n$ are composite: 15 ( $n$ = 4), 63 ( $n$ = 6), 255 ( $n$ = 8), 511 ( $n$ = 9) …. This is no coincidence.

Whenever $n$ is composite, the Mersenne number $2^n-1$ is also composite.

The fact follows from the following identity.

$\displaystyle \begin{aligned} 2^{ab}-1&=(2^a-1) \ (1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a}) \\&=(2^b-1) \ (1+2^b+2^{2b}+2^{3b}+\cdots+2^{(a-1)b}) \end{aligned}$

Thus if we are interested in finding numbers $2^n-1$ that are prime, we must start with an exponent $n$ that is prime. For ease of discussion, define $M_p=2^p-1$ and assume that $p$ is prime.

Mersenne primes have a long history. Long before the computer age, people had been doing primality testing on Mersenne numbers. The first four Mersenne primes $M_p$ , for $p$ = 2, 3, 5, and 7, were known in antiquity. The next Mersenne prime $M_{13}$ was discovered before 1461. People at that time thought that $M_p$ is prime whenever $p$ is prime. In 1536, Hudalricus Regius found that $M_{11}=2^{11}-1=2047=23 \times 89$ . In 1603, Pietro Cataldi showed that $M_p$ is prime for $p$ = 17 and 19.

The name of Mersenne prime was due to the connection with the French monk Marin Mersenne. In his 1644 book Cognita Physico-Mathematica, Mersenne stated that $M_p$ is prime when $p$ = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257. Some of these claims were later determined to be wrong. His list also missed some correct Mersenne primes. From then on, his name was attached to this particular type of prime numbers.

The next discovery of a Mersenne prime (after Pietro Cataldi), $M_{31}$ , was made by Leonhard Euler in 1772. The one found after Euler’s, $M_{127}$ , was made by Edouard Lucas in 1876. There were three more Mersenne primes discovered before the computer age – $M_{61}$ in 1883 by Ivan Pervushin, $M_{89}$ and $M_{107}$ by R. E. Powers in 1911 and 1914, respectively.

In the pre-computer age, there were long stretches of time in between discoveries of Mersenne primes. For example, it took almost 200 years after Pietro Cataldi for the next Mersenne prime to emerge (discovered by Euler). There were about 100 years in between Euler’s discovery and Lucas’ discovery.

Another important contribution made by Lucas is a test that he developed to test Mersenne numbers to see if they are prime. The test was originally developed in 1856 and later improved by him in 1878. It was further improved by Derrick Henry Lehmer in the 1930s. The test is now known as the Lucas-Lehmer test.

Lucas-Lehmer Test. Define a sequence of positive integers $S_0, S_1, S_2, S_3, \cdots$ such that $S_0=4$ and $S_j=S_{j-1}^2-2$ where $j \ge 1$ . Suppose that $p \ge 3$ . Then $M_p=2^p-1$ is a Mersenne prime if and only if $M_p$ divides $S_{p-2}$ .

To perform the test, start with $S_0=4$ and recursively calculate $S_j=S_{j-1}^2-2$ until $S_{p-2}$ is obtained. Then perform the division of $S_{p-2}$ by $M_p$ . If $S_{p-2}$ is divisible by $M_p$ , then $M_p$ is prime. If $S_{p-2}$ is not divisible by $M_p$ , then $M_p$ is composite. It is interesting that when $M_p$ is found to be composite in this manner, the compositeness of $M_p$ is established without finding any prime factors of $M_p$ .

The computer discoveries of Mersenne primes began in 1952 by Raphael Robinson. The Lucas–Lehmer test is the primality test used by the Great Internet Mersenne Prime Search (GIMPS) to discover large primes. GIMPS is a distributed computing project on the Internet for finding large prime numbers.

As of the writing of this post (May 25, 2017), a total of 49 Mersenne primes had been discovered. The latest one is $M_{74207281}$ , with over 22 million digits, which was found in January 2016.

Despite of the computation advance, there are still many fundamental questions that are still not known about Mersenne primes. For example, how many Mersenne primes are there? It is not even known whether the set of Mersenne primes is finite or infinite. It is also not known whether infinitely many Mersenne numbers with prime exponents are composite.

Because of the Lucas-Lehmer test, whenever someone finds a new largest prime number, it is usually a Mersenne prime. So every few years or so, Mersenne prime is on the news for the reason of being discovered. For up-to-date information or to learn more about basic facts, go to the Mersenne prime website and the Wikipedia entry on Mersenne primes.

____________________________________________________________________________
$\copyright$ 2017 – Dan Ma

Exploring Number Theory

A blog on elementary number theory

The quadratic reciprocity law and the supplements

More extension of quadratic reciprocity

Extending the law of quadratic reciprocity

A theorem to help find primitive roots

Finding Square Roots Modulo an Odd Composite Number

Finding Square Roots Modulo a Power of an Odd Prime

Finding Square Roots Modulo a Product of Odd Primes

Finding square roots modulo an odd prime

A 22-million digit prime number

Mersenne Prime