High School Mathematics Extensions/Further Modular Arithmetic/Multiplicative Group and Discrete Log

High School Mathematics Extensions

---

Supplementary Chapters — Primes and Modular Arithmetic — Logic

Mathematical Proofs — Set Theory and Infinite Processes — Counting and Generating Functions — Discrete Probability

Matrices — Further Modular Arithmetic — Mathematical Programming — Markov Chains

HSME
Content
Further Modular Arithmetic
Multiplicative Group and Discrete Log
Problems & Projects
Problem Set
Project
Solutions
Exercises Solutions
Problem Set Solutions
Misc.
Definition Sheet
Full Version
PDF Version

Introduction

Group theory is one of the most important mathematical theories today. ...more motivation to come

Let p be a prime then the multiplicative group mod p is the set of numbers {1, 2, .., p - 1}. As the name suggests, in a mod p group, multiplication is the main and only concern. Notice that in the multiplicative group of order p - 1, every element has an inverse. This is a key requirement for a group. In general group theory, for G to be a group, it must

1. be made up of a set of things
   • in this case the numbers 1 to p - 1,
2. have a binary operation
   • in this case multiplication,
3. be closed under the operation, i.e. if a and b are things belonging to the group then ab must also belong to the group
   • this is definitely satisfied in modulo p arithmetic
4. have an identity
   • in this case the number 1
5. every element has an inverse under the operation
   • in mod p since we have excluded 0 from the group this is satisfied.

Basically a group needs to have a 1 and every other element must have an inverse. In modular arithmetic, a group is very special because it is also commutative (ab = ba) where as for a general group, commutativity is not required. A commutative group is called an abelian group, named after the Norwegian mathematician, Abel.

On a side note, multiplicative groups modulo p have a finite number of elements. In general group theory, a group can have infinitely many elements.

info -- Abel Prize

The Abel's prize. ...more to come

The discrete log problem

Recall the log function defined in real numbers. Let b^x = y, taking the log to be base b we get x = log_b(y), so given b and y we can solve for x. But in modular arithmetics the same problem can be quite hard to solve.

Take for example, we know that 5^x ≡ 172 (mod 263) for some x. Finding the x is not easy. The most simple way seems to be trying x = 2, 3, ... and so on. In fact for p a prime, and if given a^x ≡ b, finding x is the so called discrete log problem and there is no known efficient way for solving it.

Lack of efficient algorithm is not the only problem though. Consider 2^x ≡ 5 (mod 7), there is no solution! ...more to come

We will present a quite powerful way for solving the discrete log problem a little later in the chapter, called the Pohlig-Hellman algorithm. It works by using the Chinese Remainder Theorem and breaking the problem into components. At this moment though we should try to gain some sense of just how difficult the discrete log problem is.

Exercises

1. Find x such that 3^x ≡ 6 (mod 7)

2. Find x such that 2^x ≡ 48 (mod 61)

3. Find x such that 5^x ≡ 172 (mod 263)

Order

The order of a group refers to the number of element in the group. E.g. the multiplicative group mod 17 has order 16. For a start we should only consider multiplicatives group mod a prime p, so a group has order p - 1. If G is a group then we denote the order of the group by |G|.

The order of an element, g, in a group G refers to the smallest number k ≠ 0 such that g^k ≡ 1. We denote the order of g by |g|, so g^|g| ≡ 1. There are two very important and fundamental theorems we want to discuss. The first we have met a number of times already. It states that

If G is a (finite) group and g is an element of the group, then

$g^{|G|}=1\!$

The proof of the theorem is similar to that of the FLT. Let a be an element of G and let the g_i's be the elements of G. Let's consider,

$a,ag_{1},ag_{2},ag_{3},...,ag_{|G|-1}\!$

there are |G| elements above, and they must all be different. To see this let's suppose the opposite, i.e. $g_{i}\neq g_{j}\!$ but $ag_{i}\equiv ag_{j}\!$ then since a belongs to a group, there must exist a^-1, multiply both sides by the inverse of a we get $g_{i}\equiv g_{j}\!$ which is a contradiction.

Therefore, we can say the above list is just the |G| elements of G in a different order, we get

$a(ag_{1})(ag_{2})(ag_{3})\cdots (ag_{|G|-1})\equiv g_{1}g_{2}\cdots g_{|G|-1}\!$

to save some writing, let's say

$s\equiv g_{1}g_{2}\cdots g_{|G|-1}\!$

so we have

$a^{|G|}s\equiv s\!$

but s belong to the group therefore s^-1 exists, and we get

$a^{|G|}\equiv 1\!$

as required.

The reader should be persuaded to compute the order of every element in mod 17. If that is done it should be noted that the order of every element divides 16, the order of the group. This fact is generally true and is known as the Lagrange's Theorem.

Lagrange's Theorem

Let G be a (finite) group, and let g be an element of the group.
The order of g must divide the order of the group G. More symbolically, |g| divides |G|.

We will give a proof of the above, but the reader should try and come up with their own justifications.

Proof
Let g be an element of G. We know that

$g^{|G|}\equiv 1\!$

Let's compute the remainder of |G| divided by |g|, i.e. we find r < |g| and q such that |G| = q|g| + r. So we have

$g^{|G|}=g^{|g|q+r}\equiv (g^{|g|})^{q}g^{r}\equiv g^{r}\equiv 1\!$

but r is smaller then the order of g, so r = 0. Therefore we have q|g| = |G|, and so the order of g divides the order G.

Summary

Let G be a group and g be an element of the group, then
1. g|G| = 1, and
2. |g| divides |G|

Exercises

1. Compute the order of all the elements mod 47.

2. Compute the order of all the elements mod 137.

3. The number 3 has order 16 mod 17. Find all the other elements in mod 17 with order 16.

Generator

We have shown that in mod 17, the number 3 has order 16. This is actually very interesting, because it says that every element in the mod 17 group can be expressed as a power of 3, as can be confirmed below

$3^{0}\equiv 1$

$3^{1}\equiv 3$

$3^{2}\equiv 9$

$3^{3}\equiv 27\equiv 10$

$3^{4}\equiv 30\equiv 13\equiv -4$

$3^{5}\equiv -12\equiv 5$

$3^{6}\equiv 15\equiv -2$

$3^{7}\equiv -6\equiv 11$

$3^{8}\equiv 33\equiv 16\equiv -1$

$3^{9}\equiv -3\equiv 14$

$3^{10}\equiv -9\equiv 8$

$3^{11}\equiv 24\equiv 7$

$3^{12}\equiv 21\equiv 4$

$3^{13}\equiv 12\equiv -5$

$3^{14}\equiv -15\equiv 2$

$3^{15}\equiv 6$

$3^{16}\equiv 1$

If g is so that every other element in G can be expressed as a power of g then g is called the generator of G, in the sense that g can be used to generate every other element. In other books, g may also be called a primitive element.

It is a remarkable fact that if p is a prime then the multiplicative group mod p has a generator. A proof will be given later. For now let's discuss the implications of this fact. For a start, if g is a generator, then it makes sense to talk about log to the base g, which in number theory is called the index to base g, because every element h = g^x, so ind_g(h) = x. Therefore if we are given

$h\equiv k^{x}\!$

for some unknown x, we take the index of both sides

$\operatorname {ind_{g}} (h)=x\ \operatorname {ind_{g}} (k)\!$

make x the subject, we get

$x={\frac {\operatorname {ind_{g}} (k)}{\operatorname {ind_{g}} (h)}}\!$

we have essentially converted a general discrete log problem to a discrete log problem to the base g, where g is a generator. Therefore, if we can solve the discrete log problem to a base g, then we have solved every discrete log problem.

But solving the discrete log problem to a base g (generator) is also very hard. Actually finding a generator is not easy either.

Let's get back to the mod 17. Notice that there are actually 8 generators. They are 3, 10, 5, 11, 14, 7, 12 and 6. It is not a coincidence that φ(17 - 1) also equals 8.

Exercises

1. Find all the generators of 41.

2. Given that 6 is a generator mod 41. Find the discrete log to the base 6 of 17 (mod 41).

3. How many generators are there in mod 709. Note that 708 = 2² × 3 × 59.

...more to come

Existence of a generator

In this section, we will show that there must exist a generator in mod p prime. Suppose an abelian (multiplicative) group G has order p - 1 (i.e. {1,2,3,...p - 1} are the elements of G and arithmetic is performed mod p), let g be the element of G of maximal order, i.e. |g| ≥ |h| for any element h in G.

Now consider the equation

$x^{|g|}\equiv 1{\pmod {p}}\!$

or equivalently

$x^{|g|}-1\equiv 0{\pmod {p}}\!$

the element g definitely satisfies the above equation, but so does any power of g. It can be confirmed

$(g^{a})^{|g|}\equiv (g^{|g|})^{a}\equiv 1^{a}\equiv 1\!$

in other words, we can factorise the polynomial as follows

$x^{|g|}-1=(x-1)(x-g)(x-g^{2})\cdots (x-g^{|g|-1})\equiv 0\!$

We can show that only powers of g can satisfy the above equation. Suppose otherwise, i.e. if an element h is not a power of g, but h also satifies h^|g| ≡ 1, then substitute h into the equation above, we get

$h^{|g|}-1=(h-1)(h-g)(h-g^{2})\cdots (h-g^{|g|-1})\equiv 0\!$

since by assumption h is not a power of g, so none of the terms above is zero, therefore they must have inverses. Multiply each term by its inverse. We end up with

$1\equiv 0\!$

which is absurd! Contradiction! Therefore only powers of g can satisfy x^|g| ≡ 1 (mod p).

Now if we show that every element in G must satisfy x^|g| ≡ 1, then we are done. Let's suppose there is an element h such that h does not satisfy the equation, then |h| does not divide |g|. Thereofore we must have

$|gh|={\frac {|g||h|}{\gcd {(|g|,|h|)}}}$

(see exercise if this is unclear) which is greater than |g|. But this is a contradiction of the fact that g has maximal order! Therefore every element of G must be a power of g and so g is the generator of G.

The above shows that in mod p prime, there is always a generator, but it doesn't tell us how to find one. As of today, there is no widely known efficient algorithm for finding the generator for a general p.

Exercises

0. (Optional) Show that lcm(a,b)×gcd(a,b) = ab, where lcm(x,y) denotes the lowest common multiple of x and y. E.g. lcm(5,7) = 35 and lcm(14,49) = 98.

1. Show in mod p, |ab| = lcm(|a|,|b|) where lcm(x,y) denotes the lowest common multiple of x and y. E.g. lcm(5,7) = 35 and lcm(14,49) = 98.

Subgroup

...more to come

*Pohlig-Hellman Algorithm*

We are now ready to learn about the Pohlig-Hellman algorithm for finding the discrete log. As mentioned above, it works by breaking the problem into components. We will probably need a calculator for this section.

Let's consider a simple case first. Let p = 113 and given 3 is a generator mod 113, we want to find a x such that 3^x ≡ 38. We can assume that

x = 0, 1, 2, ... , or 111

(as x¹¹² ≡ 1 ≡ x⁰ ). So x is like a value in mod 112 = 2⁴7. By the CRT x can be uniquely represented as a two-tuple.

Let's assume

$x\equiv a_{0}+2a_{1}+2^{2}a_{2}+2^{3}a_{3}{\pmod {2^{4}}}\!$

we represented x in the funny way above so that we can obtain the values more easily (as will be clear soon), and

$x\equiv b{\pmod {7}}\!$.

where $a_{i}$ takes value 0 or 1, and b takes value 0, 1, 2, 3, 4, 5, or 6.

The algorithm is completed in three stages, we will describe each in turn. Firstly, we want to compute the values of $a_{0},a_{1},a_{2}$ and $a_{3}$. We compute the following values

1. $3^{0{\frac {112}{2}}}\equiv 3^{0}\equiv 1$
2. $3^{1{\frac {112}{2}}}\equiv 3^{56}\equiv -1\equiv 112$

we did this so we can look it up later.

Now consider

$a=38^{\frac {p-1}{2}}\equiv 3^{x{\frac {p-1}{2}}}\equiv 3^{(a_{0}+a_{1}2+a_{2}2^{2}+a_{3}2^{3}){\frac {p-1}{2}}}$

and so

$a=3^{(a_{0}{\frac {p-1}{2}}+a_{1}(p-1)+a_{2}2(p-1)+a_{3}2^{2}(p-1))}\equiv 3^{(a_{0}{\frac {p-1}{2}})}$

now we compare a to the values computed above, if a equals 1 then we can conclude that $a_{0}$ = 0, otherwise if a equals -1 then we can conclude that $a_{0}$ = 1. So we have uncovered the value of $a_{0}$.

To find out $a_{1}$ we notice that

$38^{\frac {p-1}{2}}3^{-a_{0}{\frac {p-1}{2}}}\equiv 3^{(x-a_{0}){\frac {p-1}{2}}}\equiv 3^{(a_{1}(p-1)+a_{2}2(p-1)+a_{3}2^{2}(p-1))}\!$

so compute

$a\!$	$=\!$	$38^{\frac {p-1}{2^{2}}}3^{-a_{0}{\frac {p-1}{2^{2}}}}\equiv 3^{(x-a_{0}){\frac {p-1}{2^{2}}}}\!$
	$\equiv \!$	$3^{(a_{1}{\frac {p-1}{2}}+a_{2}(p-1)+a_{3}2(p-1))}$
	$\equiv \!$	$3^{(a_{1}{\frac {p-1}{2}})}\!$

now if a = 0 then $a_{1}=0$ and $a_{1}=1$ otherwise.

In the same way, compute

$38^{\frac {p-1}{2^{3}}}3^{(-a_{0}-2a_{1}){\frac {p-1}{2^{3}}}}$

and then

$38^{\frac {p-1}{2^{4}}}3^{(-a_{0}-2a_{1}-2^{2}a_{2}){\frac {p-1}{2^{4}}}}$

to determine the values of $a_{2}$ and $a_{3}$.

Now to determine the value of b. Let's compute the following 7 values

1. $3^{0{\frac {112}{7}}}\equiv 3^{0}\equiv 1$
2. $3^{1{\frac {112}{7}}}\equiv 3^{16}\equiv 49$
3. $3^{2{\frac {112}{7}}}\equiv 3^{32}\equiv 28$
4. $3^{3{\frac {112}{7}}}\equiv 3^{48}\equiv 16$
5. $3^{4{\frac {112}{7}}}\equiv 3^{64}\equiv 106$
6. $3^{5{\frac {112}{7}}}\equiv 3^{80}\equiv 109$
7. $3^{6{\frac {112}{7}}}\equiv 3^{96}\equiv 30$

then we compute

$a=38^{\frac {112}{7}}\equiv 3^{x{\frac {112}{7}}}\equiv 3^{b{\frac {112}{7}}}$

and compare with the values computed above to obtain b.

If we have computed the values of a 's correctly, then we should see that

$a_{0}=1$

$a_{1}=1$

$a_{2}=1$

$a_{3}=1$

and

b = 6.

Now solve

$x\equiv 1+2+2^{2}+2^{3}\equiv 15{\pmod {16}}\!$

$x\equiv 6{\pmod {7}}\!$

to obtain x = 111. Therefore 3¹¹¹ = 38.

The combination of simultaneous modular equations is done via chinese remainder theorem:

$x=a*7*(7^{-1}\mod {16})+b*16*(16^{-1}\mod {7}){\pmod {112}}$

$x=15*7*7+6*16*4{\pmod {112}}=111$

...more to come

Feedback

What do you think? Too easy or too hard? Too much information or not enough? How can we improve? Please let us know by leaving a comment in the discussion tab. Better still, edit it yourself and make it better.