Author 
Message 
Derek Holt science forum beginner
Joined: 14 Jan 2006
Posts: 14

Posted: Fri Jul 21, 2006 1:26 pm Post subject:
Re: Finite fields and Splitting fields



Arturo Magidin wrote:
Quote:  In article <1153420512.579184.318810@m73g2000cwd.googlegroups.com>,
vedmundson@hotmail.com> wrote:
How many elements are there in the splitting fields of the following
two polynomialsover GF(2)?
(a) x^3 + x^2 + x + 1
(b) x^3 + x^2 + 1.
I worked on this problem and these are both elements of GF(2^4). I'm
not entirely certain on how to solve this problem given that I've never
done it over a finite field.
Over GF(2^4), x^3 + x^2 + 1 = (x^2+1)(x+1) = (x+1)(x+1(x+1)
This is wrong. (x^2+1)(x+1) = x^3+x^2+x+1, not x^3+x^2+1. (Had your
factorization been correct, it would have shown the factorization can
be done over GF(2) itself, no need to go to GF(2^4).
and x^3 + x^2 + 1 = (x^2 + x)(x^2+1)
Again, this is wrong. You have
(x^2+x)(x^2+1) = x^4 + x^3 + x^2 + x, not x^3+x^2+1. Had your
factorization been correct, it would have shown that the polynomial
splits over GF(2).
I believe that I am doing this right, at least.
Alas, no.
In any case, I would
greatly appreciate any help on this problem.
Okay. Let's take x^3+x^2+1. This is irreducible over GF(2), since it
has no roots and is degree 3 (any factorization would necessarily
involve a linear factor). Letting F = GF(2), let u be a root of
x^3+x^2+1 taken in some fixed algebraic closure, and let K=F(u); then
[K:F]=3, which means that K must be GF(2^3). The question is whether
the polynomial splits over K, or if you must take a further
extension. If it splits over K, then you are done. If not, then the
polynomial must factor as (xu)g(x), where g(x) is an irreducible
quadratic, so the splitting field must be of degree 2 over K, and
therefore of degree 6 over F, meaning it will be GF(2^6). So the only
possibilities are that the splitting field of x^3+x^2+1 is degree 3
over F, in which case it has 8 elements; or else it is degree 6, in
which case it has 64 elements.
Which one is it? We know that

Rather than carry out a detailed calculation, it is probably preferable
at this stage to make use of the general result that, if F = GF(q) is
any finite field and p is an irreducible polynomial of degree n
over F, then the splitting field of p has degree n over F. This
follows easily from the fact that there is a unique finite field of any
given prime power order, because adjoining any of the n roots of p
to F must result in the same extension field GF(q^n).
Derek Holt.
Quote:  x^3+x^2+1 = (x+u)g(x) for some quadratic g(x) with coefficients in
K. We just need to figure out what g is; g(x) = x^2+sx+t, and we have
x^3+x^2+1 = (x+u)(x^2+sx+t)
= x^3 + sx^2 + tx + ux^2 + usx + ut
= x^3 + (s+u)x^2 + (t+us)x + ut.
So we must have s+u = 1, t+us = 0, ut=1. Now, the elements of K can be
written uniquely in the form a+bu+cu^2, with u^3 = u^2+1. So s = 1+u,
hence 0 = t+us = t+u(1+u) = t + u + u^2, so t = u+u^2; to verify note
that u^3+u^2 = 1, hence u(u^2+u) = 1. So t = u^2+u, as before.
Indeed:
(x+u)(x^2 + (1+u)x + (u+u^2))
= x^3 + (1+u)x^2 + (u+u^2)x
+ ux^2 + (u+u^2)x + (u^2+u^3)
= x^3 + x^2 + (u^2+u^3)
= x^3 + x^2 + 1.
Now: g(x) = x^2 + (1+u)x + (u+u^2). So you just need to check if this
polynomial has a root in K. The elements of K are of the form
a+bu+cu^2, with a, b, c in GF(2). Let r = a+bu+cu^2, and evaluate
g(r). Note that u^3 = 1+u^2 and u^4 = uu^3 = u+u^3 = 1+u+u^2.
We have:
g(r) = (a+bu+cu^2)^2 + (1+u)(a+bu+cu^2) + (u+u^2)
= a^2 + bu^2 + cu^4 + a+bu+cu^2 +au + bu^2 + cu^3 + u + u^2
= (a+a) + (b + a + 1)u + (b + c + b + 1)u^2 + cu^3 + cu^4
= (1+a+b)u + (1+c)u^2 + c(1+u^2) + c(1+u+u^2)
= (1+a+b+c)u + (1+c)u^2.
If this is going to be a root, we need c+1=0 and a+b+c+1=0.
So we must have c=1 and a+b=0.Thus the two roots we get are a=b=c=1,
and a=b=0, c=1. That is, r=1+u+u^2 and r=u^2.
For example, plug in u^2 into g. We have
g(u^2) = u^4 + (1+u)u^2 + (u+u^2)
= 1+u+u^2 + u^2+u^3 + u+u^2
= 1+u+u^2 + u^2 + 1+u^2 + u + u^2
= (1+1) + (1+1)u + (1+1+1+1)u^2 = 0.
Thus, g(x) has both roots in K already, so the splitting field of
x^3+x^2+1 is just K; hence it is degree 3 over F, and so has 8
elements.

======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
 Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================
Arturo Magidin 


Back to top 


W. Dale Hall science forum Guru
Joined: 29 Apr 2005
Posts: 350

Posted: Thu Jul 20, 2006 8:08 pm Post subject:
Re: Finite fields and Splitting fields



W. Dale Hall wrote:
Quote: 
W. Dale Hall wrote:
Some buncha stuff, leading to this:
This field has 8 elements, of course, and the polynomial
then splits into atleast a linear * quadratic. The question
arises as to whether that quadratic also splits. A quick
bit of pencil/paper work shows that the quadratic factor
is this
Q(x) = x^2 + (alpha + 1) x + (alpha^2 + 1)
Darn that paper and pencil crap, anyhow:
Q(x) = x^2 + (alpha + 1) x + (alpha^2 + alpha)
Modulo any further typos, the rest looked OK
Dale.

I suppose not. Arturo Magidin's article showed this
new and improved quadratic factor does have roots in GF(2^3).
Here they are:
alpha^2, alpha^2 + alpha + 1
where alpha is the root of the linear factor that split off
when going from GF(2) to GF(2^3).
As Arturo indicated, the quadratic *does* split in GF(2^3),
so that is indeed the splitting field.
The lesson I learn, of course, is that I should proofread,
and proofread again. Not to mention repeat computations
when the data changes.
Duh.
Dale 

Back to top 


W. Dale Hall science forum Guru
Joined: 29 Apr 2005
Posts: 350

Posted: Thu Jul 20, 2006 7:51 pm Post subject:
Re: Finite fields and Splitting fields



Arturo Magidin wrote:
Quote:  In article <l%Qvg.174711$F_3.59602@newssvr29.news.prodigy.net>,
W. Dale Hall <mailtodhall@farir.com> wrote:
Hrmph...
[.snip.]
In fact, the polynomial
P(x) = x^3 + x^2 + 1
doesn't have any roots in GF(2):
x P(x)
0 1
1 1
Since it's a cubic, the fact that it has no roots implies
that it is irreducible. You can introduce a single root by
passing to the field GF(2^3), expressible as the quotient
GF(2^3) ~ GF(2)[x]/<P(x)
where you take all polynomials over GF(2) and impose the
identity P(x) = 0, which amounts to imposing the condition
that x^3 = x^2 + 1.
This field has 8 elements, of course, and the polynomial
then splits into atleast a linear * quadratic. The question
arises as to whether that quadratic also splits. A quick
bit of pencil/paper work shows that the quadratic factor
is this
Q(x) = x^2 + (alpha + 1) x + (alpha^2 + 1)
where alpha is the name of the root of P(x) added to GF(2)
to form GF(2^3), and a bit more work shows Q(x) doesn't have
any roots in GF(2^3).
At least one of us has made a mistake, since I think I found that the
polynomial does split in GF(2^3). Hrmph.
Of course, it could be that we both made mistakes; but at least I can
rest assured that one of us is correct in our assertion. (:

My mistake. I made a mistake in computation of Q(x). I compounded it
by not repeating the calculation of Q(x) for all values of x in
GF(2^3), and so didn't correct my (now mistaken?) claim that the
polynomial didn't have its roots in GF(2^3). Rather than leave a
potential error hanging in the breeze, I'll go back and do the
calculation with the correct version of Q(x).
Since your value for g(x) is correct (and my followup to my original
reply to the OP contains that as the corrected value of Q(x)), I expect
that my next step will simply confirm your solution.
Dale. 

Back to top 


Arturo Magidin science forum Guru
Joined: 25 Mar 2005
Posts: 1838

Posted: Thu Jul 20, 2006 7:46 pm Post subject:
Re: Finite fields and Splitting fields



In article <l%Qvg.174711$F_3.59602@newssvr29.news.prodigy.net>,
W. Dale Hall <mailtodhall@farir.com> wrote:
Hrmph...
[.snip.]
Quote:  In fact, the polynomial
P(x) = x^3 + x^2 + 1
doesn't have any roots in GF(2):
x P(x)
0 1
1 1
Since it's a cubic, the fact that it has no roots implies
that it is irreducible. You can introduce a single root by
passing to the field GF(2^3), expressible as the quotient
GF(2^3) ~ GF(2)[x]/<P(x)
where you take all polynomials over GF(2) and impose the
identity P(x) = 0, which amounts to imposing the condition
that x^3 = x^2 + 1.
This field has 8 elements, of course, and the polynomial
then splits into atleast a linear * quadratic. The question
arises as to whether that quadratic also splits. A quick
bit of pencil/paper work shows that the quadratic factor
is this
Q(x) = x^2 + (alpha + 1) x + (alpha^2 + 1)
where alpha is the name of the root of P(x) added to GF(2)
to form GF(2^3), and a bit more work shows Q(x) doesn't have
any roots in GF(2^3).

At least one of us has made a mistake, since I think I found that the
polynomial does split in GF(2^3). Hrmph.
Of course, it could be that we both made mistakes; but at least I can
rest assured that one of us is correct in our assertion. (:

======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
 Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================
Arturo Magidin 

Back to top 


W. Dale Hall science forum Guru
Joined: 29 Apr 2005
Posts: 350

Posted: Thu Jul 20, 2006 7:45 pm Post subject:
Re: Finite fields and Splitting fields



W. Dale Hall wrote:
Some buncha stuff, leading to this:
Quote:  This field has 8 elements, of course, and the polynomial
then splits into atleast a linear * quadratic. The question
arises as to whether that quadratic also splits. A quick
bit of pencil/paper work shows that the quadratic factor
is this
Q(x) = x^2 + (alpha + 1) x + (alpha^2 + 1)

Darn that paper and pencil crap, anyhow:
Q(x) = x^2 + (alpha + 1) x + (alpha^2 + alpha)
Modulo any further typos, the rest looked OK
Dale. 

Back to top 


W. Dale Hall science forum Guru
Joined: 29 Apr 2005
Posts: 350

Posted: Thu Jul 20, 2006 7:41 pm Post subject:
Re: Finite fields and Splitting fields



vedmundson@hotmail.com wrote:
Quote:  How many elements are there in the splitting fields of the following
two polynomialsover GF(2)?
(a) x^3 + x^2 + x + 1

This polynomial already splits into linear factors over GF(2):
Note that over the integers, we have this:
(x + 1)^3 = x^3 + 3x^2 + 3x + 1
and reducing mod 2, it becomes this
(x + 1)^3 = x^3 + x^2 + x + 1 (mod 2)
Alternatively, you could write (again over Z)
x^3 + x^2 + x + 1 = (x^2 + 1)(x + 1)
and use the fact that over GF(2), x^2 + 1 = (x + 1)^2:
(x + 1)^3 = x^3 + x^2 + x + 1 (mod 2)
Quote:  (b) x^3 + x^2 + 1.
I worked on this problem and these are both elements of GF(2^4).

What do you mean? You've written polynomials over GF(2). They're
polynomials, not elements of some extension field. You could, I
suppose reduce them modulo some irreducible quartic polynomial
to map them to GF(2^4), but that doesn't solve any problem that
I can see.
Quote:  I'm not entirely certain on how to solve this problem given that
I've never done it over a finite field.
Over GF(2^4), x^3 + x^2 + 1 = (x^2+1)(x+1) = (x+1)(x+1(x+1)
unbalanced parentheses^^^
and x^3 + x^2 + 1 = (x^2 + x)(x^2+1) = x(x+1)(x^2+1) =
x(x+1)(x+1(x+1).

How do you get that? This factorization works for the first
polynomial (see earlier section of article), but simply
multiplying it out (over Z) you get this:
(x^2 + 1)(x + 1) = x^3 + x^2 + x + 1
and you don't get to throw the linear term out just because
you have GF(2) coefficients, so this (which is your polynomial
from the first example) isn't actually the polynomial you wish
to be working with.
Note that if a cubic polynomial factors, it must factor into
the product of a linear factor by a quadratic factor. Linear
factors are easy to spot: they correspond to roots of your
original polynomial.
In fact, the polynomial
P(x) = x^3 + x^2 + 1
doesn't have any roots in GF(2):
x P(x)
0 1
1 1
Since it's a cubic, the fact that it has no roots implies
that it is irreducible. You can introduce a single root by
passing to the field GF(2^3), expressible as the quotient
GF(2^3) ~ GF(2)[x]/<P(x)>
where you take all polynomials over GF(2) and impose the
identity P(x) = 0, which amounts to imposing the condition
that x^3 = x^2 + 1.
This field has 8 elements, of course, and the polynomial
then splits into atleast a linear * quadratic. The question
arises as to whether that quadratic also splits. A quick
bit of pencil/paper work shows that the quadratic factor
is this
Q(x) = x^2 + (alpha + 1) x + (alpha^2 + 1)
where alpha is the name of the root of P(x) added to GF(2)
to form GF(2^3), and a bit more work shows Q(x) doesn't have
any roots in GF(2^3).
Then, to get your splitting field, you need to take one
more quadratic extension, using Q(x) over GF(2^3) rather
than P(x) over GF(2).
I'll leave the rest to you.
Quote:  I believe that I am doing this right, at least. In any case, I would
greatly appreciate any help on this problem.

I hope this is understandable, and that it helps.
Dale. 

Back to top 


Arturo Magidin science forum Guru
Joined: 25 Mar 2005
Posts: 1838

Posted: Thu Jul 20, 2006 7:14 pm Post subject:
Re: Finite fields and Splitting fields



In article <1153420512.579184.318810@m73g2000cwd.googlegroups.com>,
<vedmundson@hotmail.com> wrote:
Quote:  How many elements are there in the splitting fields of the following
two polynomialsover GF(2)?
(a) x^3 + x^2 + x + 1
(b) x^3 + x^2 + 1.
I worked on this problem and these are both elements of GF(2^4). I'm
not entirely certain on how to solve this problem given that I've never
done it over a finite field.
Over GF(2^4), x^3 + x^2 + 1 = (x^2+1)(x+1) = (x+1)(x+1(x+1)

This is wrong. (x^2+1)(x+1) = x^3+x^2+x+1, not x^3+x^2+1. (Had your
factorization been correct, it would have shown the factorization can
be done over GF(2) itself, no need to go to GF(2^4).
Quote:  and x^3 + x^2 + 1 = (x^2 + x)(x^2+1)

Again, this is wrong. You have
(x^2+x)(x^2+1) = x^4 + x^3 + x^2 + x, not x^3+x^2+1. Had your
factorization been correct, it would have shown that the polynomial
splits over GF(2).
Quote:  I believe that I am doing this right, at least.

Alas, no.
Quote:  In any case, I would
greatly appreciate any help on this problem.

Okay. Let's take x^3+x^2+1. This is irreducible over GF(2), since it
has no roots and is degree 3 (any factorization would necessarily
involve a linear factor). Letting F = GF(2), let u be a root of
x^3+x^2+1 taken in some fixed algebraic closure, and let K=F(u); then
[K:F]=3, which means that K must be GF(2^3). The question is whether
the polynomial splits over K, or if you must take a further
extension. If it splits over K, then you are done. If not, then the
polynomial must factor as (xu)g(x), where g(x) is an irreducible
quadratic, so the splitting field must be of degree 2 over K, and
therefore of degree 6 over F, meaning it will be GF(2^6). So the only
possibilities are that the splitting field of x^3+x^2+1 is degree 3
over F, in which case it has 8 elements; or else it is degree 6, in
which case it has 64 elements.
Which one is it? We know that
x^3+x^2+1 = (x+u)g(x) for some quadratic g(x) with coefficients in
K. We just need to figure out what g is; g(x) = x^2+sx+t, and we have
x^3+x^2+1 = (x+u)(x^2+sx+t)
= x^3 + sx^2 + tx + ux^2 + usx + ut
= x^3 + (s+u)x^2 + (t+us)x + ut.
So we must have s+u = 1, t+us = 0, ut=1. Now, the elements of K can be
written uniquely in the form a+bu+cu^2, with u^3 = u^2+1. So s = 1+u,
hence 0 = t+us = t+u(1+u) = t + u + u^2, so t = u+u^2; to verify note
that u^3+u^2 = 1, hence u(u^2+u) = 1. So t = u^2+u, as before.
Indeed:
(x+u)(x^2 + (1+u)x + (u+u^2))
= x^3 + (1+u)x^2 + (u+u^2)x
+ ux^2 + (u+u^2)x + (u^2+u^3)
= x^3 + x^2 + (u^2+u^3)
= x^3 + x^2 + 1.
Now: g(x) = x^2 + (1+u)x + (u+u^2). So you just need to check if this
polynomial has a root in K. The elements of K are of the form
a+bu+cu^2, with a, b, c in GF(2). Let r = a+bu+cu^2, and evaluate
g(r). Note that u^3 = 1+u^2 and u^4 = uu^3 = u+u^3 = 1+u+u^2.
We have:
g(r) = (a+bu+cu^2)^2 + (1+u)(a+bu+cu^2) + (u+u^2)
= a^2 + bu^2 + cu^4 + a+bu+cu^2 +au + bu^2 + cu^3 + u + u^2
= (a+a) + (b + a + 1)u + (b + c + b + 1)u^2 + cu^3 + cu^4
= (1+a+b)u + (1+c)u^2 + c(1+u^2) + c(1+u+u^2)
= (1+a+b+c)u + (1+c)u^2.
If this is going to be a root, we need c+1=0 and a+b+c+1=0.
So we must have c=1 and a+b=0.Thus the two roots we get are a=b=c=1,
and a=b=0, c=1. That is, r=1+u+u^2 and r=u^2.
For example, plug in u^2 into g. We have
g(u^2) = u^4 + (1+u)u^2 + (u+u^2)
= 1+u+u^2 + u^2+u^3 + u+u^2
= 1+u+u^2 + u^2 + 1+u^2 + u + u^2
= (1+1) + (1+1)u + (1+1+1+1)u^2 = 0.
Thus, g(x) has both roots in K already, so the splitting field of
x^3+x^2+1 is just K; hence it is degree 3 over F, and so has 8
elements.

======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
 Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================
Arturo Magidin 

Back to top 


mariano.suarezalvarez@gma science forum addict
Joined: 28 Apr 2006
Posts: 58

Posted: Thu Jul 20, 2006 6:57 pm Post subject:
Re: Finite fields and Splitting fields



vedmundson@hotmail.com wrote:
Quote:  How many elements are there in the splitting fields of the following
two polynomialsover GF(2)?
(a) x^3 + x^2 + x + 1
(b) x^3 + x^2 + 1.

Are they irreducible over GF(2)? What is the relation between
the degree of a polynomial and the degree of its splitting field
as an extension of GF(2)? What is the relation between the degree
of an finite extension of GF(2) and its cardinality?
Quote:  I worked on this problem and these are both elements of GF(2^4). I'm
not entirely certain on how to solve this problem given that I've never
done it over a finite field.
Over GF(2^4), x^3 + x^2 + 1 = (x^2+1)(x+1) = (x+1)(x+1(x+1)
and x^3 + x^2 + 1 = (x^2 + x)(x^2+1) = x(x+1)(x^2+1) = x(x+1)(x+1(x+1).

Hmm.
You probably mean that over *GF(2)* one has
x^3+x^2+x^2+1 = (1+x)^3.
Can you see what the splitting field of
x^3+x^2+x^2+1 is with this information?
 m 

Back to top 


vedmundson@hotmail.com science forum beginner
Joined: 20 Jul 2006
Posts: 1

Posted: Thu Jul 20, 2006 6:35 pm Post subject:
Finite fields and Splitting fields



How many elements are there in the splitting fields of the following
two polynomialsover GF(2)?
(a) x^3 + x^2 + x + 1
(b) x^3 + x^2 + 1.
I worked on this problem and these are both elements of GF(2^4). I'm
not entirely certain on how to solve this problem given that I've never
done it over a finite field.
Over GF(2^4), x^3 + x^2 + 1 = (x^2+1)(x+1) = (x+1)(x+1(x+1)
and x^3 + x^2 + 1 = (x^2 + x)(x^2+1) = x(x+1)(x^2+1) = x(x+1)(x+1(x+1).
I believe that I am doing this right, at least. In any case, I would
greatly appreciate any help on this problem. 

Back to top 


Google


Back to top 



The time now is Thu Aug 24, 2017 1:10 am  All times are GMT

