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

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 bx = y, taking the log to be base b we get x = logb(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 5x ≡ 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 axb, 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 2x ≡ 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 3x ≡ 6 (mod 7)

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

3. Find x such that 5x ≡ 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 gk ≡ 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

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

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

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

to save some writing, let's say

so we have

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

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

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

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

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 = gx, so indg(h) = x. Therefore if we are given

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

make x the subject, we get

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 = 22 × 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

or equivalently

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

in other words, we can factorise the polynomial as follows

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

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

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

(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 3x ≡ 38. We can assume that

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

(as x112 ≡ 1 ≡ x0 ). So x is like a value in mod 112 = 247. By the CRT x can be uniquely represented as a two-tuple.

Let's assume

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

.

where 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 and . We compute the following values

we did this so we can look it up later.

Now consider

and so

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

To find out we notice that

so compute

now if a = 0 then and otherwise.

In the same way, compute

and then

to determine the values of and .

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

then we compute

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

and

b = 6.

Now solve

to obtain x = 111. Therefore 3111 = 38.

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

...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.