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 a^m = 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 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¹ ≡ 5 mod 13
      5² ≡ 12 mod 13
      5³ ≡ 8 mod 13
      5⁴ ≡ 1 mod 13	<--- Bingo!

      ord₁₃5 = 4

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

  What happens if we keep going?

      5⁵ ≡ 5 mod 13	<--- Repeats!
      5⁶ ≡ 12 mod 13
      5⁷ ≡ 8 mod 13
      5⁸ ≡ 1 mod 13
      5⁹ ≡ 5 mod 13	<--- Repeats!
      5¹⁰ ≡ 12 mod 13
      5¹¹ ≡ 8 mod 13
      5¹² ≡ 1 mod 13

      <4> = { 5, 12, 8, 1 }

2 mod 11

  2¹ ≡ 2 mod 11
  2² ≡ 4 mod 11
  2³ ≡ 8 mod 11
  2⁴ ≡ 5 mod 11
  2⁵ ≡ 10 mod 11
  2⁶ ≡ 9 mod 11
  2⁷ ≡ 7 mod 11
  2⁸ ≡ 3 mod 11
  2⁹ ≡ 6 mod 11
  2¹⁰ ≡ 1 mod 11	<--- Bingo!

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

  ord₁₁2 = 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:

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¹ ≡ 5 mod 13
      5² ≡ 12 mod 13
      5³ ≡ 8 mod 13
      5⁴ ≡ 1 mod 13

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

  ord₁₃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¹ ≡ 2 mod 11
      2² ≡ 4 mod 11
      2⁵ ≡ 10 mod 11
      2¹⁰ ≡ 1 mod 11

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

  ord₁₁2 = 10

Some may have noticed that the theorem to find the smallest positive integer m such that a^m ≡ 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:

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₁₁(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¹ ≡ 2 mod 13
      2⁵ ≡ 6 mod 13
      2⁷ ≡ 11 mod 13
      2¹¹ ≡ 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¹ ≡ 5 mod 23
      5³ ≡ 10 mod 23
      5⁵ ≡ 20 mod 23
      5⁷ ≡ 17 mod 23
      5⁹ ≡ 11 mod 23
      5¹³ ≡ 21 mod 23
      5¹⁵ ≡ 19 mod 23
      5¹⁷ ≡ 15 mod 23
      5¹⁹ ≡ 7 mod 23
      5²¹ ≡ 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.

Definition

Some Examples

Euler’s Totient

Primitive Roots

Conclusion

References