# Previous Classes 

## [Week 1](https://steemit.com/mathematics/@complexring/cryptography-101-an-interactive-class-an-introduction-to-group-theory--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 if`a,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!