# Groups

Groups are actually one of the first important algebraic structures, and their study was motivated by the problem of finding the formula for the root of a polynomial in terms of their coefficients. Later, mathematians turned to investigate the set of permutations of roots of a given polynomial. Eventually, Evariste Galois, founder of Group Theory, reducted the study of algebraic equations to the study of permutation groups.

Groups, and other finer structures are one of the building blocks of **public-key cryptography**.

Definition: A

groupis asetG, together with a given binary operation \(\circ\). The group and the binary operation \(\circ\) satisfy the following properties:

- The group operation \(\circ\) is
closedi.e. for all \(a, b \in G\), it holds that \(a \circ b = c \in G\).- The group operation \(\circ\) is
associativei.e. \(a \circ (b \circ c) = (a \circ b) \circ c\) for all \(a, b, c \in G\).- There is an element \(1 \in G\), called the
identity element, such that \(a \circ 1 = 1 \circ a = a\) for all \(a \in G\).- For each \(a \in G\), there exists an element \(a^{-1} \in G\), called the inverse of \(a\) such that \(a \circ a^{-1} = a^{-1} \circ a = 1\)

It is recommended to write a group as \((G, \circ)\) where \(\circ\) is the binary operation of the group.
Note: Groups can be both finite and infinite. In modern cryptography, we are almost always dealing with *finite-groups*

## Abelian Groups

Defintion: A group \((G, \circ)\) is

abelianif it also satisfies thecommutativeproperty i.e. for all \(a, b \in G\), \(a \circ b = b \circ a\)

\(\mathbb{Z}^{*}_{n}\) is an abelian group that is used in cryptographic schemes such as Diffie-Hellman Key Exchange, Elgamal Encryption, Digital Signatures, etc.

Theorem: The set \(\mathbb{Z}^{*}_{n}\) that consists of all integers \(i = 0, 1, ..., n-1\) for which the \(gcd(i, n) = 1\) forms an

abeliangroup under the binary operation multiplicaiton modulo \(n\). The identity element, of course, is 1.

## Cyclic Groups

Before we can fully understand cyclic groups, it will be helpful to brush up on other relevant definitions.

Definition: A group \((G, \circ)\) is

finiteif it has a finite number of elements. The number of elements present in the group is also referred to as thecardinalityor theorderof the group. It is denoted as \(|G|\)

**Order of an Element**

Definition: The

order of an element \(a\) of a group\((G, \circ)\) is the smallest positive integer \(k\) such that\[a^{k} = a \circ a \circ a \circ ... \circ a = 1\]

Finally,

Definition: A group \((G, \circ)\) which contains an element \(a\) with order equal to \(|G|\) is said to be

cyclic. The elements with maximum order i.e. equal to \(|G|\) are calledprimitive elementsorgenerators.

A cyclic group, along with the generator, offers interesting properties. One of those properties is that every element of the cyclic group can be generated by just raising \(a\) to various powers within the group.

Okay, so we know what a cyclic finite group is, but how to we create one? Luckily, here's a sweet little theorem.

Theorem: If \(p\) is prime, then \((\mathbb{Z}^{*}_{p}, \circ)\) is an

abelian finite groupwhere \(\circ\) is multiplication mod \(p\) binary operation.

According to the above theorem, we can create an abelian cyclic group per prime number! For instance, \(Z^{*}_{13}\) will be finite cyclic group and all the elements, together with the operation \(*\) will hold all the group properties. Finite groups over a prime \(p\) are so important and useful that almost every modern brower has a built in cyrptosystem over \(Z^{*}_{p}\).