7 min read

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.

References