02.4 Commutative Groups

Abelian Groups

Definition

A commutative group (or Abelian group) is a set $G$ which has an operation $\ast$ that combines two elements $a$ and $b$ to form $a\ast b$ In order to qualify as a commutative group, it must satisfy :

• Closure — $\forall a,b\in G,(a\ast b)\in G$
• Associativity — $\forall a,b,c\in G⟹a\ast (b\ast c)=(a\ast b)\ast c$
• Identity — There exists $e\in G$, such that $\forall a\in G$, $a\ast e=e\ast a=a$
• Inverse — $\forall a\in G$, there exists $b\in G$ such that $a\ast b=b\ast a=e$
• Commutativity — $\forall a,b\in G$, we have $a\ast b=b\ast a$

To obtain such a group within the modulo multiplication, we have to eliminate the elements that don’t have an inverse.

Theorem

For every integer $m>1$, we have the commutative group $(\mathbb{Z}/m{\mathbb{Z}}^{\ast },\cdot )$

Proof

⇒ Check the axioms

Euler’s Totient Function

Definition

We have Euler’s function $\varphi (n)$ (or Euler’s totient function), which gives the amount of positive integers that are relatively prime (coprime) to $n$

Cartesian Products

We can multiply sets together. Just as such, we can have the cartesian multiplication of two abelian groups.

We have $(G,\ast )=(G_1,{\ast }_1)\times (G_2,{\ast }_2)$ is the set $G=G_1\times G_2$ with the operation $(a_1{\ast }_1{b}_1,a_2{\ast }_2{b}_2)$

Theorem

The cartesian multiplication of two commutative groups, is a commutative group

Isomorphism

Definition

An isomorphism of two sets (which both have a binary operation $(G,\ast )$ and $(H,\otimes )$), is a bijection $\psi :G\to H$ such that

$$\psi (a\ast b)=\psi (a)\otimes \psi (b)$$

If this isomorphism exists, we say that both sets are isomorphic

The Order of a Group Element

Theorem

If we have $(G,\ast )$ a finite commutative group, with the identity element $e$ For every $a\in G$, we have an integer $k>1$, where $a\ast a\ast \cdots \ast a=e$, with $k$ being the number of repetitions

We use the notation $a^k:=a\ast a\ast \cdots \ast a$

Definition

Let $(G,\ast )$ be a finite commutative group, and let $a\in G$ The smallest positive integer $k$, such that $a^k=e$ is called the order of $a$

Theorem

Two finite commutative groups are isomorphic ⇐> they have the same multiset of orders

Theorem

An integer $k$ satisfies $a^k=e$ ⇐> the order $j$ of $a$ divides $k$ ($j\times n=k,n\in \mathbb{N}$)

Langrage’s theorem

Theorem

For an abelian group of cardinality $n$, each element’s order divides $n$

Equivalence relation and Equivalence classes

Relations in mathematics are represented by a binary relation. (We have seen this last semester)

Definition

A relation on a set $A$ is called an equivalence relation if it is reflexive, symetric, and transitive

For an element $a\in A$, we denote its equivalence class as

$$[a]=\{b\in A:b\sim a\}$$

We can use these elements to represent the class. $[b]$ and $[a]$ are the same class (provided $b\in a$)

Finding inverse elements within a group

Corollary

Consider a finite commutative group $(G,\star )$, with $n$ elements. For any $b\in G$, we have the inverse element given by

$$b^{-1}=b^{n-1}$$

Euler’s theorem

Corollary

Using Euler’s totient function, we find that:
Let $m\ge 2$ be an integer. For all $a\in (\mathbb{Z}/m{\mathbb{Z}}^{\ast },\cdot )$, we have

$$a^{\varphi (m)}=[1{]}_m$$

Equivalently, we have that for all integers $a$ that are relatively prime with $m$,

$$a^{\varphi (m)}\equiv 1\mathrm{mod}m$$

Fermat’s theorem

Theorem

Let $p$ be prime. For all $a\in (\mathbb{Z}/p\mathbb{Z},\cdot )$, we have

$$a^p=a$$

Equivalently, for all $a\in \mathbb{Z}$, we have

$$a^p\equiv a\mathrm{mod}p$$

Cyclic groups

We have a finite abelian group $(G,\star )$ or $n$ elements, with an element $g$ of order $n$ ⇒ We call this a cyclic group of generator $g$

This set contains the elements $G=\{g,g^2,g^3,\dots ,g^n\}$

Propriety

All cyclic groups are isomorphic

The order for any $b\in G$, we have, with $b=g^i$

$$\text{order}(b)=\frac{\text{lcm}(i,n)}{i}=\frac{n}{\gcd (i,n)}$$

Using Euler’s totient function, we have $\varphi (n)$ the number of generators of the cyclic group.

Discrete Logarithms

The discrete exponentiation to the base $b$ of a cyclic group is given by

$$\begin{array}{lrcl}f:& \mathbb{Z}/n\mathbb{Z}& \to & G\\ & [i{]}_n& \mapsto & b^i\end{array}$$

We therefore also have the inverse mapping

$$\begin{array}{lrcl}{f}^{-1}:& G& \to & \mathbb{Z}/n\mathbb{Z}\\ & a=b^i& \mapsto & [i{]}_n\end{array}$$

We call this mapping the discrete logarithm to the base $b$, and we write it as

$$[i{]}_n={\log }_{b}a$$

02.5 Public Key Cryptography