How can we find a generator of the multiplicative group of a finite field?

[evinda]

Hello! (Wave)

I want to construct the field $\mathbb{F}_{3^3}$ and find a generator of $\mathbb{F}_{3^3}^{\star}$.

I thought to consider a $t \in \mathbb{F}_3[x]$ where $t$ is irreducible and $\deg t=3$.

So we consider $t=x^3+x^2-x+1$.

Let $b$ be a root of $t$. Then $b^3+b^2-b+1=0 \Rightarrow b^3=-b^2+b-1$.

So $\mathbb{F}_{3^3}=\{ 0,1,2,b, 2b, 2b+1, 2b+2, b^2, b^2+1, b^2+2, 2b^2, 2b^2+1, 2b^2+2\}$.

Is it right so far?
If so, how can we find a generator of $\mathbb{F}_{3^3}^{\star}$?

 

[Opalg]

Hello! (Wave)

I want to construct the field $\mathbb{F}_{3^3}$ and find a generator of $\mathbb{F}_{3^3}^{\star}$.

I thought to consider a $t \in \mathbb{F}_3[x]$ where $t$ is irreducible and $\deg t=3$.

So we consider $t=x^3+x^2-x+1$.

Let $b$ be a root of $t$. Then $b^3+b^2-b+1=0 \Rightarrow b^3=-b^2+b-1$.

Very good, up to here!

So $\mathbb{F}_{3^3}=\{ 0,1,2,b, 2b, 2b+1, 2b+2, b^2, b^2+1, b^2+2, 2b^2, 2b^2+1, 2b^2+2\}$.

Is it right so far?

That can't be right! The field $\mathbb{F}_{3^3}$ should have $3^3=27$ elements, but you have only listed $13$. In fact, $\mathbb{F}_{3^3} = \{xb^2 + yb + c: x,y,z\in \mathbb{F}_3\}$.

If so, how can we find a generator of $\mathbb{F}_{3^3}^{\star}$?

I expect some algebra expert will come up with a systematic way to do this. My method was simply to guess that $b$ is a generator of $\mathbb{F}_{3^3}^{\star}$. The order of $b$ in $\mathbb{F}_{3^3}^{\star}$ must divide the order of the group, which is $26$. So it must be $2$, $13$ or $26$.

Clearly $b^2\ne1$, so the order of $b$ is not $2$. You can calculate $b^{13}$ in various ways, repeatedly using the fact that $b^3=-b^2+b-1$. It turns out that $b^{13} = -1$. Thus the order of $b$ is not $13$ and must therefore be $26$. In other words, $b$ is a generator.

 

[evinda]

That can't be right! The field $\mathbb{F}_{3^3}$ should have $3^3=27$ elements, but you have only listed $13$. In fact, $\mathbb{F}_{3^3} = \{xb^2 + yb + c: x,y,z\in \mathbb{F}_3\}$.

You meant $\mathbb{F}_{3^3} = \{xb^2 + yb + z: x,y,z\in \mathbb{F}_3\}$, right?

How do we know that the set $ \{xb^2 + yb + z: x,y,z\in \mathbb{F}_3\}$ contains $27$ elements?
I thought that there are $3$ possible values for $x$, two for $a^2$, $3$ for $x$, $3$ for $a$ and $3$ for $z$, so in total $3 \cdot 2+ 3 \cdot 3+3=18$. Am I wrong? (Sweating)

I expect some algebra expert will come up with a systematic way to do this. My method was simply to guess that $b$ is a generator of $\mathbb{F}_{3^3}^{\star}$. The order of $b$ in $\mathbb{F}_{3^3}^{\star}$ must divide the order of the group, which is $26$. So it must be $2$, $13$ or $26$.

Clearly $b^2\ne1$, so the order of $b$ is not $2$. You can calculate $b^{13}$ in various ways, repeatedly using the fact that $b^3=-b^2+b-1$. It turns out that $b^{13} = -1$. Thus the order of $b$ is not $13$ and must therefore be $26$. In other words, $b$ is a generator.

So does this mean that any element in this field ,the order of which will be $26$, will be a generator of the field?

 

[Opalg]

You meant $\mathbb{F}_{3^3} = \{xb^2 + yb + z: x,y,z\in \mathbb{F}_3\}$, right?
Yes, sorry about the typo.

How do we know that the set $ \{xb^2 + yb + z: x,y,z\in \mathbb{F}_3\}$ contains $27$ elements?
The field $\color{green}{\mathbb{F}_{p^k}}$ always contains $\color{green}p^k$ elements.

I thought that there are $3$ possible values for $x$, two for $a^2$, $3$ for $x$, $3$ for $a$ and $3$ for $z$, so in total $3 \cdot 2+ 3 \cdot 3+3=18$. Am I wrong? (Sweating)
There are three choices for each of $\color{green}x,y,z$ in the expression $\color{green}xb^2 + yb + z$, making 27 elements altogether.

So does this mean that any element in this field, the order of which will be $26$, will be a generator of the field?
Yes.

. . .

 

[Deveno]

Very good, up to here!

That can't be right! The field $\mathbb{F}_{3^3}$ should have $3^3=27$ elements, but you have only listed $13$. In fact, $\mathbb{F}_{3^3} = \{xb^2 + yb + c: x,y,z\in \mathbb{F}_3\}$.

I expect some algebra expert will come up with a systematic way to do this. My method was simply to guess that $b$ is a generator of $\mathbb{F}_{3^3}^{\star}$. The order of $b$ in $\mathbb{F}_{3^3}^{\star}$ must divide the order of the group, which is $26$. So it must be $2$, $13$ or $26$.

Clearly $b^2\ne1$, so the order of $b$ is not $2$. You can calculate $b^{13}$ in various ways, repeatedly using the fact that $b^3=-b^2+b-1$. It turns out that $b^{13} = -1$. Thus the order of $b$ is not $13$ and must therefore be $26$. In other words, $b$ is a generator.

It turns out that "guess and check" is still the best way, finding generators of finite cyclic groups is known to be "computationally hard".

 

[evinda]

You can calculate $b^{13}$ in various ways, repeatedly using the fact that $b^3=-b^2+b-1$. It turns out that $b^{13} = -1$. Thus the order of $b$ is not $13$ and must therefore be $26$. In other words, $b$ is a generator.

How can we calculate $b^{13}$ ?

I tried the following:
$b^{13}=b^3 b^3 b^3 b^3 b=(-b^2+b-1)^4 a=(a^4-2a^3+3a^2-2a+1)(a^4-2a^3+3a^2-2a+1) a$

But I think that this doesn't help. Or does it? (Thinking)

 

[Opalg]

How can we calculate $b^{13}$ ?

Here's what I did, starting from $b^3 = -b^2+b-1$. Multiply that by $b$ to get $$b^4 = - b^3 + b^2 - b = -(-b^2+b-1) + b^2 - b = 2b^2 - 2b + 1.$$ Next, $$b^6 = b^2b^4 = b^2(2b^2 - 2b + 1) = 2b^4 - 2b^3 + b^2 = 2(2b^2 - 2b + 1) -2(-b^2+b-1) + b^2 = b^2+1.$$ Then $$b^{12} = (b^6)^2 = (b^2+1)^2 = b^4 + 2b^2 + 1 = (2b^2 - 2b + 1) + 2b^2 + 1 = b^2 - 2b + 2$$ and finally $$b^{13} = bb^{12} = b(b^2 - 2b + 2) = b^3 - 2b^2 + 2b = (-b^2+b-1) - 2b^2 + 2b = -1.$$

 

[evinda]

Here's what I did, starting from $b^3 = -b^2+b-1$. Multiply that by $b$ to get $$b^4 = - b^3 + b^2 - b = -(-b^2+b-1) + b^2 - b = 2b^2 - 2b + 1.$$ Next, $$b^6 = b^2b^4 = b^2(2b^2 - 2b + 1) = 2b^4 - 2b^3 + b^2 = 2(2b^2 - 2b + 1) -2(-b^2+b-1) + b^2 = b^2+1.$$ Then $$b^{12} = (b^6)^2 = (b^2+1)^2 = b^4 + 2b^2 + 1 = (2b^2 - 2b + 1) + 2b^2 + 1 = b^2 - 2b + 2$$ and finally $$b^{13} = bb^{12} = b(b^2 - 2b + 2) = b^3 - 2b^2 + 2b = (-b^2+b-1) - 2b^2 + 2b = -1.$$

Ah, I see... So since we guess that $b$ is a generator of the field and we verify that $b^{26}=1$ we know that there is no $n < 26$ such that $b^n=1$ ? (Thinking)

 

[Deveno]

Ah, I see... So since we guess that $b$ is a generator of the field and we verify that $b^{26}=1$ we know that there is no $n < 26$ such that $b^n=1$ ? (Thinking)

With a cyclic group, we do not have to check *every* power less than the order, only DIVISIORS of said order.

In fact, it suffices to check MAXIMAL DIVISORS, that is, if our order is $n$, then $d$ such that $n/d$ is prime.

Since $26$ is of the form $pq$ for the primes $p = 2$ and $q = 13$, these are the maximal divisors, and are the only two powers we need to verify are not the identity.

 

[evinda]

With a cyclic group, we do not have to check *every* power less than the order, only DIVISIORS of said order.

In fact, it suffices to check MAXIMAL DIVISORS, that is, if our order is $n$, then $d$ such that $n/d$ is prime.

Since $26$ is of the form $pq$ for the primes $p = 2$ and $q = 13$, these are the maximal divisors, and are the only two powers we need to verify are not the identity.

Don't we also have to check if $b^1=1$ ?

How do we know that $\mathbb{F}_{3^3}^{\ast}$ is a cyclic group?

 

[Deveno]

Don't we also have to check if $b^1=1$ ?

How do we know that $\mathbb{F}_{3^3}^{\ast}$ is a cyclic group?

Those are insightful questions.

The first I can answer easily:

If $b = 1$, then $1$ would be a root of $x^3+x^2−x+1$, but we see:

$1^3 + 1^2 - 1 + 1 = 1 + 1 - 1 + 1 = 1 + 1 = 2 \neq 0 \in \Bbb Z_3$.

The second I don't have room to fully answer in a post, but it is a theorem that the multiplicative group of every finite field is cyclic. A proof of this can be found here:

http://www.math.wm.edu/~vinroot/430S13MultFiniteField.pdf

The basic idea is that the multiplicative group of a finite field is a finite abelian group, and such groups have special properties.

Other proofs often invoke the Structure Theorem for finite abelian groups. This says that any finite abelian group can be written as a direct product of cyclic groups.

Another proof (based on a counting argument) is here:

abstract algebra - Finite subgroups of the multiplicative group of a field are cyclic - Mathematics Stack Exchange

I urge you to study this well, this fact is central to important parts of number theory, as well as the particular application here.

 

[evinda]

Those are insightful questions.

The first I can answer easily:

If $b = 1$, then $1$ would be a root of $x^3+x^2−x+1$, but we see:

$1^3 + 1^2 - 1 + 1 = 1 + 1 - 1 + 1 = 1 + 1 = 2 \neq 0 \in \Bbb Z_3$.

I see... (Nod)

The second I don't have room to fully answer in a post, but it is a theorem that the multiplicative group of every finite field is cyclic. A proof of this can be found here:

http://www.math.wm.edu/~vinroot/430S13MultFiniteField.pdf

The basic idea is that the multiplicative group of a finite field is a finite abelian group, and such groups have special properties.

Other proofs often invoke the Structure Theorem for finite abelian groups. This says that any finite abelian group can be written as a direct product of cyclic groups.

Another proof (based on a counting argument) is here:

abstract algebra - Finite subgroups of the multiplicative group of a field are cyclic - Mathematics Stack Exchange

I urge you to study this well, this fact is central to important parts of number theory, as well as the particular application here.

Ok, I will read the proofs. So if we have a cyclic group, any element of the group will have an order that divides the order of the group, right?
If we have a group that is not cyclic, could an element of the group have an order that doesn't divide the order of the group? (Thinking)

 

[Deveno]

I see... (Nod)
Ok, I will read the proofs. So if we have a cyclic group, any element of the group will have an order that divides the order of the group, right?
If we have a group that is not cyclic, could an element of the group have an order that doesn't divide the order of the group? (Thinking)

No. This result is a basic one, and is an immediate corollary to Lagrange's Theorem.

 

[evinda]

With a cyclic group, we do not have to check *every* power less than the order, only DIVISIORS of said order.

In fact, it suffices to check MAXIMAL DIVISORS, that is, if our order is $n$, then $d$ such that $n/d$ is prime.

So this would hold for any finite group? (Thinking)

 

[Deveno]

Yes, and no.

If a given element is not the identity for maximal divisors of the order, it must have order equal to the order of the group-that is, it is a generator for the group, which is therefore cyclic.

However, this test could fail, we could try a maximal divisor, say $d$, and find $x^d = e$. This does not tell us the group is cyclic, or even what order $x$ has, it just tells us that $x$ is NOT a generator, and that the order of $x$ is a divisor of $d$.

So, for example, in $S_4$ (the symmetric group on four letters), we have $|S_4| = 24$, and the maximal divisors are $12$ and $8$.

It turns out that no element has order $12$, in fact, no element even has order $6$. And no element has order $8$, either. In fact the only orders are, per cycle type:

$(a\ b\ c\ d)$ which has order $4$
$(a\ b\ c)$ which has order $3$
$(a\ b)(c\ d)$ which has order $2$
$(a\ b)$ which has order $2$
$\text{id}$ which has order $1$.

To make a long story short, testing maximal divisors of the order of the group is of most use when a group is cyclic (and not every group is).

However, when the order of a group is $pq$, for $p,q$ distinct primes, we can be assured that our group is indeed cyclic (to prove this I'd need to prove Cauchy's theorem, which I don't feel like doing at the moment, or even on a higher level, the Sylow theorems, which again I do not feel like going into-it would be a *really* long post).

The abelian case is easier, one can use the Chinese Remainder Theorem to show an abelian group of order $pq$ is cyclic rather easily, but even this intermediate step is not a *short* proof.

So...yes, you can use this method on ANY finite group...BUT: it may not tell you very much (some groups are "bad"-they are VERY non-abelian (a small center) with many elements of low order, and few or no elements of the higher orders).