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
- be made up of a set of things
- in this case the numbers 1 to p - 1,
- have a binary operation
- in this case multiplication,
- 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
- have an identity
- in this case the number 1
- 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
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,
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 = g^{x}, so ind_{g}(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 = 2^{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
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 3^{x} ≡ 38. We can assume that
- x = 0, 1, 2, ... , or 111
(as x^{112} ≡ 1 ≡ x^{0} ). So x is like a value in mod 112 = 2^{4}7. 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 3^{111} = 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.