Let's discuss more about primitive root with an example.

Given our modulus of five,

which is a prime number,

let's look at how different bases A mod P behave when taking exponents.

When the base, base A is equal to one taking the exponents,

produces the same value as one,

because one raised to the power of any exponent is equal to one.

When the bases A is A equals to two,

then A to the second power mod five is equal to four,

because two squared is equal to four.

When the exponent is three,

A to the third power mod five is three,

because two to the third power is equal to eight and eight mod five is three.

When the exponent is four,

eight to the fourth power mod P is equal to one,

because two to the fourth power is equal to 16,

and 16 mod five is equal to one.

What would happen with eight to the fifth power mod P?

This is equal to eight to the fourth power mod P times

A mod P. So this is one times two mod P,

which is equal to two, and since,

eight to the sixth power mod P is equal to eight the fifth power mod P times eight mod P,

which is equal to four,

we now have a repetition.

When A is equal to two,

taking the exponent where the exponents increase,

will generate a sequence that repeats 2-4-3-1.

Therefore, there is no need to continue populating the table to

the right after the exponent four.

We can continue populating the table with the base of A is equal to three,

and A is equal to four.

Now, let's study the table that we populated.

When A is equal to one,

one value of one repeats itself with a period of one.

So this is the only value,

regardless of the value of the exponent,

or which column it is in the table.

When A is equal to four,

the sequence of four and one repeats itself,

and the values of two and three never appear when varying the exponents.

What we want are the base As that yields

all possible values when taking the exponent mod P, except for zero.

In other words, the primitive root is a number whose power

successively generate all the elements mod P, except for zero.

Because it generates all the elements mod P,

such base is appropriate for cryptographic applications.

When the modulus is P equals five,

A is equal to two, and A is equal to three, accomplishes this feature.

And these values of As are called,

the primitive root of P. In other words, in this example,

two is a primitive root of five,

and three is also a primitive root of five,

but one and four are not primitive roots of five.

Such numbers, two and three in this case,

are also called the generators,

when used in cryptography.

When a modulus P is used,

where P is a prime number,

and A is the primitive root of that P,

then the discrete logarithm,

base A mod P of Y,

exists and is unique.

In this table, the discrete log corresponds to the exponent.

For example, focusing on the four in the second column,

and the third row, the discrete log base three mod five of four is equal to two.