**How the RSA Algorithm Works**

**Portuguese Version of This Page**

**Group Theory Computational Exercise: Order of an Element
of a Group**

7/2/17 Robleh Wais

*Summary:*

*Undergraduate
mathematics majors that take a course in Group Theory study the properties of objects
known as groups. Groups have four
defining axioms. They are as follow:*

*A
group is a set G that is closed under a binary operation (like + or *).*

*The
set G has an identity element e, such that element a*e= a*

*The
members of set G are associative.That
is, for three members a, b and c the following equality holds: (a*b)*c =
a*(b*c)*

*For
every a in G there exist an element a ^{-1}
such that a* a^{-1}= e *

*In
number theory, a subdivision of mathematics associated with Group Theory,
groups are composed of integers that have an even more intriguing property,
called the order of an element. This
property is an integer that represents a count of successive exponentiations of
an integer member in a group until it terminates in the identity element of the
group. It is performed on a modulus of
group. Below, I illustrate several examples of this computation and give some
details on how to calculate the order of an element in a group correctly. *

The first step is to
enumerate the elements of the group depending on the modulus chosen.The enumeration is accomplished by listing
the elements of the group in ascending order that are relatively prime and **less **than the given number. Relatively prime means that none of the
elements have more than 1 or themselves as a divisor.

Example U(10) = (1,3,7,9)

*Note:
If you are unsure of the elements of a group under modulo you can find them by
performing the operations below for each element less than N, the group
cardinality. If the number does not eventually come to 1, the identity element,
it is not a part of the group. In the case below the numbers 2,4,6,8 are not
part of the group U(10). The numbers 2
and 5 are not part of the group because they don't satisfy the condition of
being a number less than the group cardinality and relatively prime to it. Since 2 divides 10 evenly there is no
remainder, so its not relatively prime to 10.*

To find the order of these elements calculate
successive exponentiations of that element until the identity element is
reached, i.e.,1. The calculation is based on the modulus of the group. In the
above case, the mod is 10. Add the exponentiations and the sum is the order of
that element in the modulus group.

What is the order of the elements in U(10) above.

Let's compute each element except 1, which is a
trivial case. The order of 3 in mod 10
is

3^{1}= 3, 3^{2} = 1.So, the order of 3 is 2, the sum of each
exponentiation performed.

The order of 7 in mod 10 is

7^{1}=7, 7^{2}=9, 7^{3}=3, 7^{4}=1
So, the order of 7 is 4

The order of 9 in mod 10 is

9^{1}=9, 9^{2}=1. The order of 9 is 2

We can practice this with other groups. Let's choose another group at random, find
its elements and then calculate the order of each element in the group.

How 'bout an easy one.

U(6)= (1, 5).
2, and 3 are out because they evenly divide 6, and 4 is out because it
is not relatively prime with 6 since 2 divides 6 and 4.

Again, 1 is trivial so we'll skip it.

The order of 5 in mod 6 is

5^{1}=1, order is 1 since 6-5=1

Now for a more expansive group, we'll tackle
U(21). We can find which elements are in
the group by simply trying those we are not sure of, after we eliminate the
obvious ones. Anything that divides 21 evenly is not in the group. So, 3 and 7
are out. Of course, 1 is trivial. We can
start with the following and eliminate anything for which successive exponentiations
does not result in the identity element.
The mod is 21.

U(21)=(2,4,5,8,10not all listed here)

The calculation of the order of 2 mod 21 is

2^{1}=2, 2^{2}=4, 2^{3}=8, 2^{4}=16,
2^{5}=11, 2^{6}=1

The order of 2 mod 21 is 6

Is 4 in the group? Lets find out

4^{1}=4, 4^{2}=16, 4^{3}=1 It
is, and the order mod 21 is 3

*Note:
a computational trick is to compute the power over the mod, divide by the mod,
drop the remainder and multiply the result by mod. Then subtract this result
from the original mod if you get one, you're finished. Let's see this in action
above with 4.*

*4 ^{3}=
64/21=3.0476. drop the remainder it is 3. 3*21=63. 64-63=1*

*Clearly
this applies after you've exceeded the value of the modulus number.*

Let's try 5.

5^{1}=5, 5^{2}=3, 5^{3}=20, 5^{4}=16,
5^{5}=17, 5^{6}=1 (using the technique shown above 5^{6}=15625/21=744.0476
≈744*21=15624; 15625-15624=1)

The order of 5 mod 21 is 6

Let's try 6

This computation never results in the identity element
and thus 6 is not in the group. And it is true because 6, and 21 have more than
1 as prime divisors, they share 3. The
same is true for 9,12, , 14, 15 and 18.
These numbers share other divisors with 21. For instance, 14 has 7 as a
divisor. Try the computation above on
any of these elements and it will never reduce to the identity element 1. What is left in our group after these
realizations?

U(21)= (2,4,5,
8,10,11,13,16,17,19,20)

All the above numbers should reduce to the identity
element after successive exponentiations of each element. But, since you don't believe me, and I don't
believe me we'll do them all. Alrighty?

8^{1}=8, 8^{2}=1. The order of 8 mod 21 is 2

10^{1}=10, 10^{2}=16, 10^{3}=13,
10^{4}=4, 10^{5}=19, 10^{6}= 1 The order of 10 mod 21
is 6

So far, so good

11^{1}=11, 11^{2}=16, 11^{3}=8,
11^{4}=4, 11^{5}=2, 11^{6}=1. The order of 11 mod 21 is 6

13^{1}=13 13^{2}=1 The order of 13 mod
21 is 2

16^{1}=16, 16^{2}=4, 16^{3}=1 The
order of 16 mod 21 is 3

17^{1}=17, 17^{2}=16, 17^{3}=20,
17^{4}=4, 17^{5}=5, 17^{6}=1 The order of 17 mod 21 is
6

19^{1}=19, 19^{2}=4, 19^{3}=3,
19^{4}=16, 19^{5}=10, 19^{6}=1 The order of 19 mod 21
is 6

20^{1}=20, 20^{2}=1 The order of 20
mod 21 is 2

There you have it, a relatively large collection of
ordinal elements. There are no more
elements of order in this group, and just as obvious, this is a finite
group. We can build a subset collection
of elemental ordinals for U(21). Here
they are:

U(21)_{ordinals }= (2,3,6) Notice that this set is composed of
only 3 members. Since the members occur
repeatedly in the ordinal calculations, only their unique occurrences have been
kept.

Now there is a lot more I could say about this
result. What does it imply? What if we don't remove the ordinals that
occurred repetitively? Are there any
cyclic implications in these calculations?
But, I"ll leave all these questions for another essay.

Return to Portal Philosophies, Science, Mathematics, and Music

The Existential Concept The Existential Concept