Group theory is a deep pool, and today I’m going to dip in my big toe and cover a very tiny aspect of it: the order of an element of a group. This concept is fundamental to group theory, and I’m always seeing it referenced in articles and posts on cryptography and abstract algebra.

Let’s go, I like the math life, baby!

## Definition

Let’s first understand the order of a group, denoted as `ord(G)`

or `|G|`

. This simply means the cardinality of a group, or the total number of its elements.

Now, the order of an element is different from the order of a group. Denoted as `ord(a)`

or `|a|`

, it is the smallest positive integer of the set where `a`

, where ^{m} = e`e`

is the identity element of the group (0 for addition operations and 1 for multiplication). Importantly, if no integer `m`

exists for the group, then the group has infinite order.

Since I’m interested in how the order of an integer relates to modern cryptography, all of my examples will be over modulo

`n`

.The order of

`a modulo n`

is denoted as`ord`

._{n}(a)

## Some Examples

In the following examples, we’ll be looking for the smallest positive integer that satisfies:

`a`

^{m} ≡ 1 mod n

Let’s look at an example:

`5 mod 13`

Let's try the exponents in sequential order: 5

^{1}≡ 5 mod 13 5^{2}≡ 12 mod 13 5^{3}≡ 8 mod 13 5^{4}≡ 1 mod 13 <--- Bingo!**ord**( So, we say that the order of 5 modulo 13 is 4. ) What happens if we keep going? 5_{13}5 = 4^{5}≡ 5 mod 13 <--- Repeats! 5^{6}≡ 12 mod 13 5^{7}≡ 8 mod 13 5^{8}≡ 1 mod 13 5^{9}≡ 5 mod 13 <--- Repeats! 5^{10}≡ 12 mod 13 5^{11}≡ 8 mod 13 5^{12}≡ 1 mod 13 <4> = { 5, 12, 8, 1 }`2 mod 11`

2

^{1}≡ 2 mod 11 2^{2}≡ 4 mod 11 2^{3}≡ 8 mod 11 2^{4}≡ 5 mod 11 2^{5}≡ 10 mod 11 2^{6}≡ 9 mod 11 2^{7}≡ 7 mod 11 2^{8}≡ 3 mod 11 2^{9}≡ 6 mod 11 2^{10}≡ 1 mod 11 <--- Bingo! Note that this will repeat as well, but only after every element of the group has been represented.**ord**( So, we say that the order of 2 modulo 11 is 10. ) <10> = { 2, 4, 8, 5, 10, 9, 7, 3, 6, 1 }_{11}2 = 10

This last example is particularly interesting. Did you notice that every number in the group is represented? When this occurs, we refer to the order as a primitive root of modulo n. In this instance, the order of the element equals the order of the group:

`|a| = |G|`

Now, let’s look at some other ways we can determine the order of an element.

In the worst case, this method requires a search of the entire space of

`n-1`

.

## Euler’s Totient

Another interesting method of determining the order of an element is by using Euler’s totient function. This is a faster method, for we don’t need to check every element in order in a “brute-force” approach and will only need to check the integers that are divisors of ϕ(n).

Let’s look at a theorem that uses Euler’s totient:

ord_{n}(a) | ϕ(n) iff gcd(a, n) = 1

This says that the order of `a modulo n`

divides `ϕ(n)`

if and only if their greatest common divisor is 1.

Instead of searching the entire space for an integer

`m`

where a^{m}≡ 1 mod n, we only search by the divisors that evenly divide the result of`ϕ(n)`

!

This makes more sense with some examples.

`5 mod 13`

gcd(5, 13) = 1 Get a set of all numbers relatively prime to the modulus: ϕ(13) = 12 Get the integers that divide evenly into 12: 1 2 3 4 6 12 We have 6 candidates: 5

^{1}≡ 5 mod 13 5^{2}≡ 12 mod 13 5^{3}≡ 8 mod 13 5^{4}≡ 1 mod 13 5^{4}is congruent to 1 mod 13, we can stop without having to calculate all 6!**ord**_{13}5 = 4`2 mod 11`

gcd(2, 11) = 1 Get a set of all numbers relatively prime to the modulus: ϕ(11) = 10 Get the integers that divide evenly into 10: 1 2 5 10 We have 4 candidates: 2

^{1}≡ 2 mod 11 2^{2}≡ 4 mod 11 2^{5}≡ 10 mod 11 2^{10}≡ 1 mod 11 In this case, we calculated every candidate before finding one that works.**ord**_{11}2 = 10

Some may have noticed that the theorem to find the smallest positive integer

`m`

such that`a`

is very similar to Euler’s theorem:^{m}≡ 1 mod n

`a`

^{ϕ(n)}≡ 1 mod nWhile Euler’s theorem will give us an integer that is congruent to

`1 mod n`

(when`a`

and`n`

are relatively prime, of course), it may not give us thesmallestpositive integer.

## Primitive Roots

This is a topic that really requires its own post, but it’s worth mentioning here in this context because an order of an element can also be a primitive root.

If an integer `a`

is relatively prime to `p`

and `p`

is prime, then the following defines a **primitive root modulo p**:

`ord`

_{p}(a) = ϕ(p) = p - 1

This is fairly intuitive.

Recall earlier we had the following example where we found 2 to be a primitive root modulo 11:

`2 mod 11`

ord

_{11}(2) = ϕ(11) = 11 - 1 = 10

Easy peasy.

**Theorem**: There are `ϕ(ϕ(n))`

primitive roots modulo `n`

.

How many primitive roots modulo 13?

ϕ(ϕ(13)) = ϕ(12) = 12(1 - 1/2)(1 - 1/3) = 12(1/2)(2/3) = 4

How many primitive roots modulo 23?

ϕ(ϕ(23)) = ϕ(22) = 22(1 - 1/2)(1 - 1/11) = 22(1/2)(10/11) = 10

That’s great, but how do you actually determine the primitive roots? We can use the reduced residue system!

Given the primitive root 2, find the other primitive roots mod 13.

ϕ(ϕ(13)) = ϕ(12) = 4 Use the reduced residue system mod ϕ(13). - What are the prime factors of 12? 2 3 - Filter all the integers from the set that are multiples of those prime factors, i.e., where `gcd(k, n) != 1`: { 1, 5, 7, 11 } Next, raise the known primitive root to those integers: 2

^{1}≡ 2 mod 13 2^{5}≡ 6 mod 13 2^{7}≡ 11 mod 13 2^{11}≡ 7 mod 13 In order, the other primitive roots are: { 2, 6, 7, 11 }Given the primitive root 5, find the other primitive roots mod 23.

ϕ(ϕ(23)) = ϕ(22) = 10 Use the reduced residue system mod ϕ(23). - What are the prime factors of 22? 2 11 Filter all the integers from the set that are multiples of those prime factors, i.e., where `gcd(k, n)`: { 1, 3, 5, 7, 9, 13, 15, 17, 19, 21 } Next, raise the known primitive root to those integers: 5

^{1}≡ 5 mod 23 5^{3}≡ 10 mod 23 5^{5}≡ 20 mod 23 5^{7}≡ 17 mod 23 5^{9}≡ 11 mod 23 5^{13}≡ 21 mod 23 5^{15}≡ 19 mod 23 5^{17}≡ 15 mod 23 5^{19}≡ 7 mod 23 5^{21}≡ 14 mod 23 In order, the other primitive roots are: { 5, 7, 10, 11, 14, 15, 17, 19, 20, 21 }

Oftentimes, you’ll only need to try a handful of integers in the space

`p-1`

before you find a primitive root modulo p.

Weeeeeeeeeeeeeeeeeeeeeeeee

## Conclusion

As I noted, this is only a brief excursion into some basic group theory, and specifically, the order of an element. I find both group theory and number theory immensely fascinating, addictive and helpful, and although I don’t necessarily “use” any of them when I’m programming, they have greatly increased my problem solving skills!

There is definitely more I’d like to cover at some point that relates to this post and to modular arithmetic in general, such as congruence classes, but that will have to wait until another post.