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

From Wikibooks, open books for an open world
Jump to: navigation, search
HSME
Content
100%.svg Further Modular Arithmetic
100%.svg Multiplicative Group and Discrete Log
Problems & Projects
100%.svg Problem Set
100%.svg Project
Solutions
100%.svg Exercises Solutions
50%.svg Problem Set Solutions
Misc.
Definition Sheet
Full Version
PDF Version

Introduction[edit]

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[edit]

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[edit]

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[edit]

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
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 gi'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 \ne 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_1g_2\cdots g_{|G| - 1} \!

to save some writing, let's say

s \equiv g_1g_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[edit]

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|})^qg^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[edit]

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[edit]

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 = gx, so indg(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[edit]

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[edit]

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[edit]

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[edit]

...more to come


*Pohlig-Hellman Algorithm*[edit]

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

x \equiv a_0 + 2a_1 + 2^2a_2 + 2^3a_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_12 + a_22^2 + a_32^3)\frac{p - 1}{2}}

and so

a = 3^{(a_0\frac{p - 1}{2} + a_1(p - 1) + a_22(p - 1) + a_32^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_22(p - 1) + a_32^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_32(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^2a_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 3111 = 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[edit]

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 section. Better still, edit it yourself and make it better.

To tell the truth ,I haven't finished it. The theories included is not difficult for me,because I have studied a little game theory .But the passage is a little long for me ,and I am not very interested in certain parts.It's maybe a little too much information for me.I will try to finish it . Thank you!