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

a^{b} \equiv c (mod n)

🔗

where either

a

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,

and the second one as finding a logarithm modulo

n .

🔗

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

g

n

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

g,

e.g.

a = g^{i}

and

c = g^{j}

for some

i, j \in Z .

Then our congruence will become

g^{i b} \equiv g^{j} (mod n)

🔗

and thinking of it as solving in the exponents

i b

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 .

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

x^{3} \equiv 5 (mod 17)

🔗

as powers of that primitive root.

🔗

The easy part is representing

x^{3};

we just say that

x \equiv 3^{i}

for some (as yet unknown)

i,

x^{3} \equiv {(3^{i})}^{3} \equiv 3^{3 i} .

🔗

The harder part is figuring out what power of

3

gives

5 .

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,

we transform

x^{3} \equiv 5 (mod 17)

🔗

into the congruence

3^{3 i} \equiv 3^{5} (mod 17) .

🔗

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):

3^{3 i} = 3^{5} \Rightarrow 3 i = 5 \Rightarrow i = 5 / 3 .

🔗

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

Z_{17} .

To be precise, everything in sight is really in

U_{17},

a cyclic group of order

ϕ (17) = 16 .

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

3 i \equiv 5 (mod 16) .

🔗

(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,

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 $4 i \equiv 5$ (mod $16$ ). However, there are no such solutions since $gcd (4, 16) = 4 ∤ 5,$ 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,$ and it turns out that $2^{6} \equiv 7,$ so we may attempt a solution. We obtain

2^{3 i} \equiv 2^{6} (mod 19) \Rightarrow 3 i \equiv 6 (mod 18),

which definitely does have solutions.

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

i \equiv 2 (mod 6)

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 [E.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 :$

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} .$ So we write $x = 3^{i}$ for some as yet unknown $i,$ and get

3^{6 i} \equiv 3^{36} (mod 49),

which gives us

6 i \equiv 36 (mod ϕ (49) = 42)

which itself reduces to

i \equiv 6 (mod 7) .

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

5^{x} \equiv 17 (mod 19) .

🔗

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 ever actually proved this.

🔗

Example 10.5.4.

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

2^{16 x} \equiv 2^{10} (mod 19)

yields

16 x \equiv 10 (mod 18) .

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

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

5^{4} \equiv 5^{13} \equiv 17 (mod 19)

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 (mod 19) .$

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

Thus our congruence becomes

2^{4 x} \equiv 2^{5} (mod 19)

which yields

4 x \equiv 5 (mod 18) .

However, since $gcd (4, 18) = 2 ∤ 5,$ 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},$ and evidently $13$ is not one of the elements in the subgroup generated by $16 .$ )