# Mathematical Cryptography II

## Group Theory

A **group** is a set ** G** combined with a binary operation * that satisfies the following four properties:

**Identity Law**

There is an *e ∈ G* such that *e \* a = a * e = a for every a ∈ G*.

**Inverse Law**

For every a ∈ G there is a (unique) a^−1 ∈ G satisfying;

*a \* a^−1 = a^−1 * a = e.*

**Associative Law**

*a \* (b * c) = (a * b) * c for all a, b, c ∈ G.*

**Commutative Law**

*a \* b = b * a for all a, b ∈ G*

**Addition**

Set: All integers

*{... -2, -1, 0, 1, 2, ...}*Operation: +

Identity Element: 0

Inverse Element: for every

*a ∈ G*, its inverse is*-a*

**Modular Arithmetic Addition**

Set: Integers modulo

*n: {0, 1, 2, 3..., n-1}*Operation:

*+ (mod n)*Identity Element: 0

Inverse Element: For each

*a*, an integer b such that;*a + b = 0 (mod n)*

**Matrix Group Multiplication**

Set: All invertible 2 X 2 matrices over

*R*or*C*Operation: Matrix multiplication

Identity Element:

*Identity matrix = I*Inverse Element: For a

*matrix**A*, its matrix inverse such that;*A x A^-1 = I*

If the operation is commutative, the group is called an **Abelian** or **Commutative** group.

Groups can be finite or infinite. The **order** of a group is the **number of its elements.**

### What is Subgroup ?

Let **H ⊂ G a subset. We'll say that "H is a subgroup of G" if;**

*e ∈ H*H is

**closed under * operation**;

*h1, h2 ∈ H**⇾* *h1 \* h2 ∈ H*

- H is
**closed under taking inverses;**

*h ∈ H**⇾* *h^-1 ∈ H*

As an example, let's take:

*g ∈ G, g != e*

*|G| <* ** ∞** (G is a

**finite group**)

*H = {g^k : k ∈ N} = {g, g^2, g^3, g^4, ...}*

**If H is a subgroup of G, it should validate 3 rules above.**

**Proof of 1st condition**

*G* is a finite, so *H* is also a **finite set**, since *H* is a subset of *G*.

*H = {g, g^2, g^3, g^4, ...}*

The powers of the g's can not be all different because of *g^{n+1} = g^n \* g^1 = e * g^1 = g^1*. There *must* be elements like:

*R = { m ∈ N:* *g^m = g^j**for some* *1 ≤ j < m**}*

So we can define *H* like:

*H = {g, g^2, g^3, g^4, g^j, ... g^(m-1)}*

*( N*ext element of this set is *g^m = g^j* )

*g^m \* (g^j)^-1 = e*
*g^(m- j) = e*

since j < m, (m - j) *∈ N*

*e ∈ H*

**Proof of 2nd condition**

*g^l \* g^m = g^(l + m)*

**Proof of 3rd condition**

*For g^(m- j) = e, we multiply both sides by g;*

*g^(m- j) \* g = g*

*g^(m- j + 1) = g*

m - j + 1 *∈ R*

According to this equation, m must be the smallest element of *R*. So;

*m ≤ (m - j + 1) ⇾ j ≤ 1 && 1 ≤ j < m*

*j = 1*

*H = {g, g^2, g^3, ... g^(m-1)}*

Last element's power and also element number of H is (m-1)

*g^(m- j) = e ∈ H*