Skip to main content

Section 3.5 Groups

The idea behind the Elgamal cryptosystem works for any object that has the structure of \(\F_p\ad\text{:}\) that is, a collection of objects equipped with an operation that has certain mathematical properties. We introduce the notion of a group, and state the properties that the operation on a group should have first with reference to the group of units \(\F_p\ad\text{.}\)

For the group of units \(F_p\ad\text{,}\) the operation of multiplication takes two elements \(a, b\in \F_p\ad\) and produces a new element \(ab \in F_p\ad\text{.}\) Multiplication mod \(p\) in \(F_p\ad\) has the following properties:

  1. There is an element in \(1 \in \F_p\ad\text{,}\) called the identity, with the property that for all \(a \in \F_p\ad\text{,}\) we have
    \begin{equation*} a\cdot 1= 1 \cdot a = a. \end{equation*}
  2. For every element \(a \in \F_p\ad\text{,}\) there is an element \(a\inv\text{,}\) called the inverse of \(a\text{,}\) with the property that
    \begin{equation*} a \cdot a\inv = a\inv \cdot a = 1. \end{equation*}
  3. For any elements \(a, b, c \in \F_p\ad\text{,}\) we have
    \begin{equation*} a\cdot(b\cdot c) = (a\cdot b)\cdot c. \end{equation*}
  4. For any elements \(a, b \in \F_p\ad\text{,}\) we have
    \begin{equation*} a \cdot b = b \cdot a. \end{equation*}

We now generalize these properties to an abstract set \(G\text{.}\)

Definition 3.5.1.

Let \(G\) be a set of elements, and let \(\star: G \times G \to G\) be an operation that combines two elements of \(G\) into a single element in \(G\text{.}\) We say that \(G\) is a group under \(\star\) if the operation \(\star\) has the following three properties.

  1. Identity: there exists an element \(e\in G\) such that for all \(g \in G\text{,}\) we have
    \begin{equation*} g\star e = e \star g = g. \end{equation*}
  2. Inverses: for all \(g \in G\text{,}\) there exists an element \(g\inv \in G\) so that
    \begin{equation*} g \star g\inv = g\inv \star g = e. \end{equation*}
  3. Associativity: For all \(a, b, c \in G\text{,}\) we have
    \begin{equation*} a \star (b \star c) = (a \star b) \star c. \end{equation*}
If in addition it is the case that for all \(a, b \in G\) we have
\begin{equation*} a \star b = b \star a \end{equation*}
then \(G\) is called a commutative group.
The definition above presents groups with the language of multiplication. It is also common to view certain groups as equipped with addition-like operations under the structure of addition. You should think about how the properties above would change if the operation under consideration was \(\oplus\text{.}\) The following are some common examples of groups:
  • \(\Z_n\) with the operation of addition mod n.
  • \(\Z\) with the operation of addition.
  • \(\F_p\ad\) with the operation of multiplication mod \(p\text{.}\)
  • \(GL_2\text{:}\) The set of \(2\times 2\) invertible matricies with the operation of matrix multiplication - note that this group is not commutative.
  • The set \(\{1, -1, i, -i\}\) with complex multiplication.
Definition 3.5.2.
The order of a group, denoted \(\#G\) or \(\abs{G}\text{,}\) is the number of elements in \(G\text{.}\)
Definition 3.5.3.
The order of an element in a group \(G\text{,}\) if it exists, is the smallest integer \(n\) so that \(g^n = e\text{.}\)
We call a group a finite group if \(\abs G \lt \infty\text{,}\) that is, if \(G\) has a finite number of elements.
Left as an exercise. Use the division algorith.
The following theorem is one of the most important structural theorems in group theory.
To be added. The basic idea is that the previous proposition gives both that the orders are finite AND that the orders divide any power that brings the element back to \(e\text{.}\) In the commutative case, take G and aG, show the elements are distinct, mash into giant products, use commutativity to resort, get a^n = e and then invoke prop.

Exercises Exercises

3.

Let

\begin{equation*} G = \left\{\bbm a \amp a \\ a \amp a\ebm: a \in \R, a \neq 0\right\}. \end{equation*}

Show that \(G\) is a group with the operation of matrix multiplication. What are the inverses? What is the identity element? (Hint: It can't be \(I = \bbm 1 \amp 0 \\ 0 \amp 1\ebm\) because that isn't even in the set!)