NTIC A Practical Use of Primitive Roots

Section 10.5 A Practical Use of Primitive Roots

We will soon begin talking about cryptography and related matters. Before we do so, we will preview our computational needs by using primitive roots to solve some congruences in a cool way.

🔗

Suppose you want to solve a more involved congruence than the basic ones we have tackled thus far. A general form that we might want to solve would look like

$\begin{equation*} a^b\equiv c\text{ (mod }n) \end{equation*}$

🔗

where either

$a$ or

$b$ might be a variable, and

$n$ would be prime or a prime power. Here are two examples:

$x^3 \equiv 5$ (mod $17$ )
$5^x \equiv 17$ (mod $19$ )

🔗

You can think of the first one as finding a higher root modulo

$n\text{,}$ and the second one as finding a logarithm modulo

$n\text{.}$

🔗

As we will see below, our general strategy will be to find a primitive root

$g$ of

$n$ (when this is possible) and write both as powers of

$g\text{,}$ e.g.

$a=g^i$ and

$c=g^j$ for some

$i,j\in\mathbb{Z}\text{.}$ Then our congruence will become

$\begin{equation*} g^{ib}\equiv g^j\text{ (mod }n) \end{equation*}$

🔗

and thinking of it as solving in the exponents

$ib$ and

$j$ will be productive.

🔗

Subsection 10.5.1 Finding a higher root

🔗

With that as introduction, let's examine one way to solve the first congruence using this idea.

🔗

First, find a primitive root modulo

$17\text{.}$ Obviously we could just ask Sage and its builtin command primitive_root, or use Lemma 10.2.3 with trial and error. In the not too distant past, the back of every number theory text had a table of primitive roots!

xxxxxxxxxx
 
primitive_root(17)

🔗

Now what we will do is try to represent both sides of

$\begin{equation*} x^3\equiv 5\text{ (mod }17) \end{equation*}$

🔗

as powers of that primitive root.

🔗

The easy part is representing

$x^3\text{;}$ we just say that

$x\equiv 3^i$ for some (as yet unknown)

$i\text{,}$ so

$\begin{equation*} x^3\equiv \left(3^i\right)^3\equiv 3^{3i}\text{.} \end{equation*}$

🔗

The harder part is figuring out what power of

$3$ gives

$5\text{.}$ Again, there is no shortcut, though number theory texts in the past had huge tables of them, and their powers (for easy reference). In practice, one would have all powers of a given primitive root available for use ahead of time.

xxxxxxxxxx
 
a=mod(3,17)
L=[(i,a^i) for i in range(2,17)]
for item in L:
    if item[1]!=5:
        pretty_print(html(r"$%s^{%s}\equiv %s\not\equiv 5$"%(a,item[0],item[1])))
    else:
        pretty_print(html(r"$%s^{%s}\equiv %s$ - hooray!"%(a,item[0],item[1])))
        break

🔗

By substituting the primitive roots in for

$x^3$ and

$5\text{,}$ we transform

$\begin{equation*} x^3\equiv 5\text{ (mod }17) \end{equation*}$

🔗

into the congruence

$\begin{equation*} 3^{3i}\equiv 3^{5}\text{ (mod }17)\text{.} \end{equation*}$

🔗

This is a much more familiar type of problem. How would we have solved this in high school? You would solve it this way, with equations (not congruences):

$\begin{equation*} 3^{3i}=3^{5}\Rightarrow 3i=5 \Rightarrow i=5/3\text{.} \end{equation*}$

🔗

We will try to do something very similar here.

🔗

What is very important is that this congruence is, in some sense, really no longer a congruence in

$\mathbb{Z}_{17}\text{.}$ To be precise, everything in sight is really in

$U_{17}\text{,}$ a cyclic group of order

$\phi(17)=16\text{.}$ But a cyclic group of order

$16$ would just be the same as thinking modulo sixteen! So we can take out the exponents, just like in precalculus, but do things (mod

$16$ ):

$\begin{equation*} 3i\equiv 5\text{ (mod }16)\text{.} \end{equation*}$

🔗

(See Exercise 10.6.14 to justify doing this manipulation.)

🔗

A little guess and check (or more powerful methods earlier in the book) show that

$i=7$ suffices, so that

$x=3^{7}\equiv 11$ (mod

$17$ ) is the solution. And we figured it out without taking every cube out there!

🔗

Indeed, doing just that confirms our result. We take all cubes starting at

$2\text{,}$ and the one corresponding to

$11$ is what we want:

xxxxxxxxxx
 
[mod(i,17)^3 for i in range(2,17)]

🔗

Note the use of range from Sage note 2.1.3. Why do you think we used it here?

🔗

Example 10.5.1.

If we change the congruence to a fourth power $x^4 \equiv 5$ (mod $17$ ), the only change is that now we have to solve $4i\equiv 5$ (mod $16$ ). However, there are no such solutions since $\gcd(4,16)=4\nmid 5\text{,}$ and we confirm this by seeing that $5$ does not show up in this list:

xxxxxxxxxx
 
[mod(i,17)^4 for i in range(2,17)]

🔗

Example 10.5.2.

Finally, let's try solving the closely related $x^3\equiv 7$ (mod $19$ ). Here, a primitive root is $2\text{,}$ and it turns out that $2^6\equiv 7\text{,}$ so we may attempt a solution. We obtain

$\begin{equation*} 2^{3i}\equiv 2^6\text{ (mod }19)\Rightarrow 3i\equiv 6\text{ (mod }18)\text{,} \end{equation*}$

which definitely does have solutions.

In fact, there are three solutions ( $2,8,14$ ) to the reduced congruence

$\begin{equation*} i\equiv 2\text{ (mod }6) \end{equation*}$

so there are three solutions ( $2^2,2^8,2^{14}$ ) to the original congruence. Let's check this:

xxxxxxxxxx
 
a = mod(2,19)
[(a^b)^3 for b in [2, 8, 14]]

🔗

A similar strategy can work for higher degree congruences. (See [C.2.4, Theorem 8.17] for a general statement on when such solutions exist, which we will omit for the sake of space.)

🔗

Example 10.5.3.

If we try solving $x^6\equiv 8$ (mod $49$ ), we'll need a primitive root of 49; 3 works. I can find out what power $3^i$ of $3$ yields $8\text{:}$

xxxxxxxxxx
 
x = mod(primitive_root(49),49)
L=[(i,x^i) for i in range(2,euler_phi(49))]
for item in L:
    if item[1]!=8:
        pretty_print(html(r"$%s^{%s}\equiv %s\not\equiv 8$"%(x,item[0],item[1])))
    else:
        pretty_print(html(r"$%s^{%s}\equiv %s$ - hooray!"%(x,item[0],item[1])))
        break

Looks like it's $3^{36}\text{.}$ So we write $x=3^i$ for some as yet unknown $i\text{,}$ and get

$\begin{equation*} 3^{6i}\equiv 3^{36}\text{ (mod }49)\text{,} \end{equation*}$

which gives us

$\begin{equation*} 6i\equiv 36\text{ (mod }\phi(49)=42) \end{equation*}$

which itself reduces to

$\begin{equation*} i\equiv 6\text{ (mod }7)\text{.} \end{equation*}$

So $i=6,13,20,27,34,41$ all work, which means that $x=3^{i}\equiv 43,10,16,6,39,33$ all should work.

xxxxxxxxxx
 
[mod(d,49)^6 for d in [43,10,16,6,39,33]]

🔗

Subsection 10.5.2 Discrete logarithms

🔗

Similarly, we can try to solve logarithmic examples like

$\begin{equation*} 5^x\equiv 17\text{ (mod }19)\text{.} \end{equation*}$

🔗

Indeed, solving this problem is an example of what is called a discrete logarithm problem. Such problems are apparently very, very hard to solve quickly, but (!) no one has every actually proved this.

🔗

Example 10.5.4.

Let's solve $5^x\equiv 17\text{ (mod }19)\text{.}$ As we noted in Example 10.5.2, a primitive root modulo 19 is 2, and we can check that $5\equiv 2^{16}\text{ (mod }19)$ and $17\equiv 2^{10}\text{ (mod }19)\text{.}$ Then, replacing these, we see that

$\begin{equation*} 2^{16x}\equiv 2^{10}\text{ (mod }19) \end{equation*}$

yields

$\begin{equation*} 16x\equiv 10\text{ (mod }18)\text{.} \end{equation*}$

Since each of the numbers in this latter congruence is even, we can reduce this to $8x\equiv 5$ (mod $9$ ), which further reduces to the easy-to-solve $-x\equiv 5$ (mod $9$ ).

Taking $x\equiv -5\equiv 4\text{,}$ and keeping in mind the original modulus of $18\text{,}$ that suggests that we could let $x\equiv 4,13$ in solving the original congruence. And indeed

$\begin{equation*} 5^4\equiv 5^{13}\equiv 17 \text{ (mod }19) \end{equation*}$

as desired:

xxxxxxxxxx
 
mod(5,19)^13, mod(5,19)^4

🔗

Sage note 10.5.5. Reminder on equality.

To check whether two things are equal, remember that you can just use == with the two expressions and see if you get True or False.

🔗

Example 10.5.6.

Let's try to solve $16^x\equiv 13\text{ (mod }19)\text{.}$

Again, $2$ is a primitive root of $19\text{,}$ and obviously $16=2^4\text{.}$ It might look harder to represent $13\text{;}$ of course we could do it with the computer, but note that $13+19=32=2^5\text{.}$ Sometimes we really can do them by hand!

Thus our congruence becomes

$\begin{equation*} 2^{4x}\equiv 2^{5}\text{ (mod }19) \end{equation*}$

which yields

$\begin{equation*} 4x\equiv 5\text{ (mod }18)\text{.} \end{equation*}$

However, since $\gcd(4,18)=2\nmid 5\text{,}$ by Proposition 5.1.1 this latter congruence has no solutions, so neither does the original congruence. (It turns out that $16$ has only order $9$ as an element of $U_{19}\text{,}$ and evidently $13$ is not one of the elements in the subgroup generated by $16\text{.}$ )