Groups

We define a group as a (non-empty) set \( G \) together with a binary operation (that is, an operation that takes two input elements from the set \( G \)) \( \times \) satisfying:

• G1: If \( a \) and \( b \) are in the set, then \( a\times b=c \) is also in the set.
• G2: There is an identity element, \( e \), such that \( e\times a=a\times e=a \).
• G3: If \( a \) is in the set, there is some \( b \) in the set such that \( a\times b=e \). We say that \( b \) is the inverse of \( a \) and denote it \( b=a^{-1} \).
• G4: For \( a,b,c \), \( a\times (b\times c)=(a\times b)\times c \).

The notation in groups is sometimes confusing and people can freely use additive (+) or multiplicative (\( \times \)) notation, and call their identities either \( 0 \) or \( 1 \). This doesn't matter much, since the binary operation can be quite weird (such as "addition" on elliptic curves). If you can start by looking at things a little bit more abstractly, it will pay off very quickly.

\( \mathbb{Z}/n\mathbb{Z} \) as a group. Cyclic groups.

You will frequently see these sets are denoted as \( \mathbb{Z}/p\mathbb{Z} \). We have to be very careful if we want to work with \( n \) not prime in \( \mathbb{Z}/n\mathbb{Z} \) (in this case, it is not a finite field either). For example, let's try to solve this equation: \( (x+2)\times(x+1)\equiv 0 \pmod{12} \) We could use our knowledge of math and, when the product of two numbers is \( 0 \), at least one of them is \( 0 \) (spoiler's alert: this will go wrong):

1. \( (x+2)\equiv 0 \pmod{12} \). If \( x=10 \), then \( x+2=12\equiv 0 \), since it is divisible by 12.
2. \( (x+1)\equiv 0 \pmod{12} \). If \( x=11 \), then \( x+2=12\equiv 0 \), since it is divisible by 12. Let's pick now \( 2 \) and see what happens: \( (2+2)\times(2+1)=12\equiv 0 \pmod{12} \). So \( 2 \) is a solution to the equation, but \( 2+2\equiv 4\not\equiv 0 \) and \( 2+1\equiv 3\not\equiv 0 \). This happens because \( 12 \) is not a prime number.

As a matter of fact, given \( a \) and \( n \), we have that \( a \) has an inverse (modulo \( n \)) if and only if \( gcd(a,n)=1 \), that is, \( a \) and \( n \) are coprime. In the previous example, \( 3 \) is not coprime to \( 12 \) (they have \( 3 \) as a common divisor).

If the set is not too large, we can find inverses just by trial and error. However, it would be nice to have some results that help us compute inverses and how to calculate (integer) powers of numbers.

Let's focus on a prime number \( p \) and take all the non-zero elements of the set, \( (\mathbb{Z}/p\mathbb{Z})^\star \). Let's fix \( p=7 \), so \( (\mathbb{Z}/p\mathbb{Z})^\star={1,2,3,4,5,6} \) and let's focus on multiplication over the set. We can define the power \( a^n=a\times a\times a\times ...\times a \). Obviously, \( 1 \) is not interesting, because \( 1^n=1 \), so let's take \( 5 \): \( 5^1\equiv 5 \pmod{7} \) \( 5^2\equiv 4 \pmod{7} \) \( 5^3\equiv 6 \pmod{7} \) \( 5^4\equiv 2 \pmod{7} \) \( 5^5\equiv 3 \pmod{7} \) \( 5^6\equiv 1 \pmod{7} \) \( 5^7\equiv 5 \pmod{7} \) \( 5^8\equiv 4 \pmod{7} \) \( 5^{13}\equiv 5 \pmod{7} \) We see that the powers of \( 5 \) span all the elements of the group. We also see that numbers repeat themselves at an interval of \( 6 \), that is \( 4=5^2=5^8=5^{14}... \). Let's look at \( 3 \): \( 3^1\equiv 3 \pmod{7} \) \( 3^2\equiv 2 \pmod{7} \) \( 3^3\equiv 6 \pmod{7} \) \( 3^4\equiv 4 \pmod{7} \) \( 3^5\equiv 5 \pmod{7} \) \( 3^6\equiv 1 \pmod{7} \) \( 3^7\equiv 3 \pmod{7} \) We got all the elements (albeit in a different order). Finally, let's look at \( 2 \): \( 2^1\equiv 2 \pmod{7} \) \( 2^2\equiv 4 \pmod{7} \) \( 2^3\equiv 1 \pmod{7} \) \( 2^4\equiv 2 \pmod{7} \) This time we didn't span all the elements of the group and we got to the same number after \( 3 \). We will show that these results are valid in general (provided we're working modulo a prime number).

First, we can prove that the set \( (\mathbb{Z}/p\mathbb{Z})^\star \) together with multiplication forms an abelian group (the product can never give 0 since all the numbers are not divisible by \( p \)). Second, the group is finite, since the number of elements is finite (6 in our example); its order is \( 6 \). We also saw that by repeatedly multiplying \( 5 \) by itself (that is, taking powers of \( 5 \)), we can generate all the elements of the group (note that everything repeats after \( 6 \), which is the order of the group). Since the group can be generated by one of its elements, it is a (finite) cyclic group.

For an element \( a \), the lowest positive integer \( n \) such that \( a^n\equiv 1 \pmod{p} \) is known as the order of \( a \). The elements of the group with their respective order in parentheses are: \( 1 (1) \), \( 2 (3) \), \( 3 (6) \), \( 4 (2) \), \( 5(6) \), \( 6(2) \). We can see that the orders of each element divide the order of the group, \( 6 \). We will present the following theorems, which show that this is not a coincidence.

Subgroups. Lagrange's theorem

We saw that the order of \( (\mathbb{Z}/7\mathbb{Z})^\star \) was 6 and that if we take any element \( a \), doing \( a^6\equiv 1 \pmod{7} \). However, for \( 2 \) we can do \( 2^3\equiv 1 \pmod{7} \). A subgroup \( H \) is a subset of \( G \), that is itself a group, that is, satisfies G1-G4. For example, if we consider the subset \( H={1} \), this is a subgroup of order \( 1 \). Why? Because \( 1\times 1=1 \), so the operation is closed and all other properties follow from the operations of the group \( G \). \( G \) is also a subgroup of itself. These two are called the trivial subgroups of \( G \) (which are not very interesting). The set \( {1,2,4} \) is a subgroup of \( (\mathbb{Z}/7\mathbb{Z})^\star \). To check this, we need to see that if an element is in the set, so is its inverse, the identity belongs to the set and the operation is closed. Let's check this:

• \( 1 \) is in the set and \( 1 \) is its own inverse.
• The operation is closed, because \( 2\times 2\equiv 4 \pmod{7} \), because \( 4\times 4=16\equiv 2 \pmod{7} \) and because \( 2\times 4=8\equiv 1 \pmod{7} \) (we don't need to check the products with \( 1 \) since that is obvious). We also checked the inverses, since \( 4=2^{-1} \).

The subset \( {1,2,4} \) forms a subgroup of order \( 3 \). Lagrange's theorem states that the order of a subgroup divides the order of the group. We have another subgroup \( {1,6} \), which is of order \( 2 \). These are non-trivial subgroups. If the order of a group is prime, then its only subgroups are the trivial subgroups (since \( p \) is prime, the subgroups can only be of order \( 1 \) and \( p \)). A group whose only subgroups are the trivial ones is known as a simple group. For example, \( \mathbb{Z}/7\mathbb{Z} \) with addition is the group \( {0,1,2,3,4,5,6} \) of order \( 7 \). There are no subgroups other than the whole group and \( {0} \). Note that the order of each element (other than zero, which has order \( 1 \)) is \( 7 \), since \( 7\times a=a+a+a+a+a+a+a \) is divisible by \( 7 \) and, therefore, congruent to \( 0 \) modulo \( 7 \). The fact that some groups can be broken down into smaller subgroups is of concern when working with elliptic curves: if the group is not of prime order, it can be broken down into smaller groups and an attacker may break the system by performing searches on these subgroups.