Previous Classes

Week 1

Last week, we were introduced to the basics of group theory. We defined a group, which is a set of objects with certain properties (most notably with an operation we call + or *, the existence of inverses and identities, the associativity property, and closure), abelianity (or commutativity), gave several examples of groups, and had some (very simple) exercises.

Week 2

This week, we will go over subgroups, group isomorphisms, cyclic groups, direct products of groups, and groups of prime order.

Order of a group

First, we need to define the order of a finite group. The order of a finite group G is nothing more than the cardinality of the set G, or, in simpler words, the number of unique elements that make up the set G.

The order of a group G is denoted as either #G or |G|.

So, for instance, S_3 has order 6. S_4 has order 24. In fact, it turns out that S_n has order n!.

Exercise : Prove S_n has order n!.

Group Isomorphisms

Next, we introduce the term isomorphism, which comes from the Greek meaning same (iso-) shape (morphism). Essentially, saying two groups are isomorphic is a fancy way of saying that the groups are the same group (even if they are represented differently).

Formally, two groups, G_1 and G_2 are isomorphic if there exists a function f : G_1 -> G_2 such that f is one-to-one and onto, i.e. injective and surjective (also known as bijective), and ifa,b in G_1, then f(a*b) = f(a)*f(b).

When a function f has the property f(a*b) = f(a)*f(b), we say that f is a homomorphism.

A trick in proving group isomorphisms is showing that you can construct a bijective function f that maps the right generators of G_1 to G_2. Similarly, one can show that two groups are not isomorphic by showing that there does not exist a function f that maps generators of G_1 to generators of G_2.

Subgroups

A (proper) subgroup is a (proper) subset of elements of a group that is a group when inheriting the same group operation.

Equivalently, H is a subgroup of a group G if and only if the following holds :

a, b in H implies that a * b^{-1} in H.

Proof:

=> Assume H is a subgroup of G. Suppose a, b in H. Then, b^{-1} in H, since H is a group and inverse elements exist and a * b^{-1} in H since H is a group and * is a closed operation.

<= Suppose a, b in H implies that a*b^{-1} in H. Let a in H. Then, a * a^{-1} = 1 in H. Since 1 (the identity) is in H and a in H, then 1*a^{-1} = a^{-1} in H. So, arbitrary inverses are in H. Now, we just need to show closure. Suppose a, b in H, then b^{-1} in H and thus
a*(b^{-1})^{-1} = a*b in H, by our assumption.

Some facts and definitions

Any group is a subgroup of itself (but, by definition is not a proper subgroup).

The group consisting solely of the identity element is known as the trivial group and is a subgroup of every group.
The identity is also known as the trivial element.

Exercise : Prove that the even integers is a subgroup of the integers.

Exercise : Construct some nontrivial proper subgroups.
Hint: The integers are a proper subgroup of the rational numbers. The rational numbers are a proper subgroup of what group?

Cyclic Groups

An element g of a finite group G of order n is a generator of G if and only if n is the smallest positive integer such that g^n = 1. We say that g generates G and will often write <g> = G. We also say that the element g has order n.

A cyclic group is a finite group that is generated by at least one element. A group of order n generated by g is cyclic because g^{n+1} = g, i.e. we observe a cycle in how the group operates.

The set of integers modulo a number n is an example of a cyclic group, under the operation + with 0 acting as the identity. We denote these groups by Z_n or Z/nZ.

In addition, if h in G, we can consider the subgroup generated by h or<h> = H.

Theorem 1

Suppose G is a finitely generated group of order n and H is a subgroup of G of order k. Then, k divides n.

Proof : Exercise.

Theorem 2

All cyclic groups of order n are isomorphic to Z_n.

Proof : Exercise.

Additional exercise : Prove that S_3 is not isomorphic to Z_6.

Direct Products of Groups

Two (or a countable number of) groups can be used to construct different groups. Consider two groups G_1 and G_2 under the operations + and *, respectively. Then, G = G_1 x G_2 is a group with the operation . where g = (g_1,g_2), h = (h_1,h_2) in G and g.h = (g_1 + h_1, g_2*h_2).

Groups of Prime Order

A group of prime order is a finite group with order p such that p is a prime number.

Groups of prime order are interesting due to the following :

Theorem 3:

Every finite abelian group G is isomorphic to a direct product of cyclic groups of prime power order.

Proof : Bonus Exercise.

Hint : Apply Theorem 2

Example 1. Consider Z_6 and Z_2 x Z_3.

We claim that these two groups are isomorphic under the isomorphism:

f : Z_6 -> Z_2 x Z_3 with f(1) = (1,1), f(2) = (0,2), f(3) = (1,0), f(4) = (0,1), f(5) = (1,2), f(0) = (0,0).

One can easily verify (and should!) that f is bijective and a homomorphism.

However, once Theorem 2 has been proven, we can apply it to this example and more easily show that Z_6 and Z_2 x Z_3 are isomorphic.

Theorem 4

All groups of prime order are cyclic groups.

Proof : Exercise.

Theorem 5

All nontrivial elements of a group of prime order are generators of the group.

Proof : Exercise.

Conclusion

Why all this background in group theory?

The reasons are at least 5-fold :

1. Slowly introduce terminology,
2. These objects are building blocks to understand the basics of Elliptic Curves because
3. All elliptic curves are either a cyclic group or a product of two cyclic groups (cool, huh?!)
4. An Elliptic Curve defined over a finite field F_p is a group satisfying particular geometric properties.
5. So you can ask me questions!!!!

Before we can begin to understand Elliptic Curves defined over finite fields, we will need to go over the basics of field theory. Topics include : field definition, finite fields of characteristic p with p a prime, fields defined over prime powers, the characteristic of a field, and residues of a field.

Stay tuned for the next week's edition of Cryptography 101!