A major distinction we can draw is between a finite and an infinite group. The former has a finite number of elements, while the latter has an infinite number of elements. The number of elements in any finite group is known as the order of the group. All practical cryptography that involves the use of groups relies on finite (number-theoretic) groups.

Within public key cryptography, a certain class of finite Abelian groups known as cyclic groups are particularly important. In order to understand cyclic groups, we first need to understand the concept of group element exponentiation.

Suppose a group with a group operation , and that is an element of . The expression should, then, be interpreted as the element combined with itself a total of times. For instance, means , means , and so on. (Note that exponentiation here is not necessarily exponentiation in the standard arithmetic sense.)

Let's turn to an example. Suppose that , and that our value for equals 4. In this case, . Alternatively, would represent .

Some Abelian groups have one or more elements, which can yield all other group elements through continued exponentiation. These elements are called generators or primitive elements.

An important class of such groups is , where is a prime number. The notation here means that the group contains all non-zero, positive integers less than . Such a group, therefore, always has elements.

Consider, for instance, . This group has the following elements: . The order of this group is 10 (which is indeed equal to ).

Let's explore exponentiating the element 2 from this group. The calculations up until are shown below. Note that on the left side of the equation, the exponent refers to group element exponentiation. In our particular example, this indeed involves arithmetic exponentiation on the right side of the equation (but it could have also involved, for instance, addition). To clarify, I have written out the repeated operation, rather than the exponent form on the right side.

If you look carefully, you can see that performing exponentiation on the element 2 cycles through all the elements of in the following order: 2, 4, 8, 5, 10, 9, 7, 3, 6, 1. After , continued exponentiation of the element 2 cycles through all the elements again and in the same order. Hence, the element 2 is a generator in .

Though has multiple generators, not all the elements of this group are generators. Consider, for example, the element 3. Running through the first 10 exponentiations, without showing the cumbersome calculations, yields the following results:

Instead of cycling through all the values in , exponentiation of the element 3 only leads to a subset of those values: 3, 9, 5, 4, and 1. After the fifth exponentiation, these values start repeating.

We can now define a cyclic group as any group with at least one generator. That is, there is at least one group element from which you can produce all other group elements through exponentiation.

You may have noticed in our example above that both and equal . In fact, though we will not perform the calculations, the exponentiation by 10 of any element in the group will yield . Why is this the case?

This is an important question, but it takes some work to answer.

To start, suppose two positive integers and . An important theorem in number theory states that has a multiplicative inverse modulo (that is, an integer so that ) if and only if the greatest common divisor between and equals 1. That is, if and are coprimes.

So, for any group of integers equipped with multiplication modulo , only the smaller coprimes with are included in the set. We can denote this set by .

For instance, suppose that is 10. Only the integers 1, 3, 7, and 9 are coprimes with 10. So the set only includes . You cannot create a group with integer multiplication modulo 10 using any other integers between 1 and 10. For this particular group, the inverses are the pairs 1 and 9, and 3 and 7.

In the case where itself is prime, all the integers from 1 through are coprimes with . Such a group, thus, has an order of . Using our earlier notation, equals when is prime. The group we selected for our earlier example, , is a particular instance of this class of groups.

Next, the function calculates the number of coprimes up until a number , and is known as Euler’s Phi function. [1] According to Euler’s Theorem, whenever two integers and are coprimes, the following holds:

This has an important implication for the class of groups where is prime. For these groups, group element exponentiation represents arithmetic exponentiation. That is, represents the arithmetic operation . As any element in these multiplicative groups is coprime with , it means that .

Euler’s theorem is a really important result. To start, it implies that all elements in can only cycle through a number of values by exponentiation that divides into . In the case of , this means that each element can only cycle through 2, 5, or 10 elements. The group values that any element cycles through upon exponentiation is known as the order of the element. An element with an order equivalent to the order of a group is a generator.

Furthermore, Euler’s theorem implies that we can always know the result of for any group where is prime. This is so regardless of how complicated the actual calculations might be.

For instance, suppose our group is (where 160,481,182 is indeed a prime number). We know that all integers 1 through 160,481,181 must be elements of this group, and that . Though we cannot make all the steps in the calculations, we know that expressions such as , , and must all evaluate to .

[1] The function works as follows. Any integer can be factored into a product of primes. Suppose that a particular is factored as follows: where all the ’s are prime numbers and all the ’s are integers greater than or equal to 1. Then:

Euler's Phi function formula for the prime factorization of .