On the Order of an Element

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 `am = e`, where `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 `ordn(a)`.

Some Examples

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

`am ≡ 1 mod n`

Let’s look at an example:

• `5 mod 13`

```  Let's try the exponents in sequential order:

51 ≡ 5 mod 13
52 ≡ 12 mod 13
53 ≡ 8 mod 13
54 ≡ 1 mod 13	<--- Bingo!

ord135 = 4

( So, we say that the order of 5 modulo 13 is 4. )

What happens if we keep going?

55 ≡ 5 mod 13	<--- Repeats!
56 ≡ 12 mod 13
57 ≡ 8 mod 13
58 ≡ 1 mod 13
59 ≡ 5 mod 13	<--- Repeats!
510 ≡ 12 mod 13
511 ≡ 8 mod 13
512 ≡ 1 mod 13

<4> = { 5, 12, 8, 1 }
```
• `2 mod 11`

```  21 ≡ 2 mod 11
22 ≡ 4 mod 11
23 ≡ 8 mod 11
24 ≡ 5 mod 11
25 ≡ 10 mod 11
26 ≡ 9 mod 11
27 ≡ 7 mod 11
28 ≡ 3 mod 11
29 ≡ 6 mod 11
210 ≡ 1 mod 11	<--- Bingo!

Note that this will repeat as well, but only after
every element of the group has been represented.

ord112 = 10

( So, we say that the order of 2 modulo 11 is 10. )

<10> = { 2, 4, 8, 5, 10, 9, 7, 3, 6, 1 }
```

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:

```ordn(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 am ≡ 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:

51 ≡ 5 mod 13
52 ≡ 12 mod 13
53 ≡ 8 mod 13
54 ≡ 1 mod 13

54 is congruent to 1 mod 13, we can stop without
having to calculate all 6!

ord135 = 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:

21 ≡ 2 mod 11
22 ≡ 4 mod 11
25 ≡ 10 mod 11
210 ≡ 1 mod 11

In this case, we calculated every candidate before
finding one that works.

ord112 = 10
```

Some may have noticed that the theorem to find the smallest positive integer `m` such that `am ≡ 1 mod n` is very similar to Euler’s theorem:

`aϕ(n) ≡ 1 mod n`

While 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 the smallest positive 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:

`ordp(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`

```  ord11(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:

21 ≡ 2 mod 13
25 ≡ 6 mod 13
27 ≡ 11 mod 13
211 ≡ 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:

51 ≡ 5 mod 23
53 ≡ 10 mod 23
55 ≡ 20 mod 23
57 ≡ 17 mod 23
59 ≡ 11 mod 23
513 ≡ 21 mod 23
515 ≡ 19 mod 23
517 ≡ 15 mod 23
519 ≡ 7 mod 23
521 ≡ 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.