Mixing
Minimal polynomials of elements in $mathbb F_16$
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
List all polynomials in $mathbb F_2[x]$ that are minimal polynomials of elements from $mathbb F_16$.
Since minimal polynomials are irreducible, this problem just asks to list irreducible polynomials of certain degrees over $mathbb F_2$. But I have a hard time realizing what degrees I should consider. Does it have to do with the fact about the orders of subfields of finite fields? I'm not sure how to apply it.
abstract-algebra polynomials field-theory finite-fields irreducible-polynomials
asked Aug 6 at 1:31
user437309
556212
add a comment |Â
up vote
3
down vote
favorite
List all polynomials in $mathbb F_2[x]$ that are minimal polynomials of elements from $mathbb F_16$.
Since minimal polynomials are irreducible, this problem just asks to list irreducible polynomials of certain degrees over $mathbb F_2$. But I have a hard time realizing what degrees I should consider. Does it have to do with the fact about the orders of subfields of finite fields? I'm not sure how to apply it.
abstract-algebra polynomials field-theory finite-fields irreducible-polynomials
asked Aug 6 at 1:31
user437309
556212
4
All elements of $mathbbF_16$ are roots of $x^16-x$. Therefore, all minimal polynomials of elements of $mathbbF_16$ are irreducible factors of $x^16-x$.
– user580373
Aug 6 at 1:48
3
Don’t forget that the degree of the minimal polynomial for $alpha$ is the degree of $Bbb F_2(alpha)$ over $Bbb F_2$. So this degree can only be $1$, $2$, or $4$. Thus aside from $x$ and $x+1$, the only irreducible linears, and $x^2+x+1$, the only irreducible quadratic, you need to find the three irreducible quartics. This is not hard, when you realize that the constant term must be $1$ and there must be an odd number of monomials.
– Lubin
Aug 6 at 2:02
After Lubin's comment the question is reduced to this. Opinions differ whether that is now a duplicate or not. I would say it is, but I don't want to be the first to cast a vote, because I have dupehammer powers here.
– Jyrki Lahtonen
Aug 6 at 7:31
Of course, spiralstotheleft's comment reduces the question to this instead. May be you could post an answer based on those? That way you get a bit more feedback on your understanding this theme, and we get this question out of the unanswered pile.
– Jyrki Lahtonen
Aug 6 at 7:32
@JyrkiLahtonen I've posted an answer below. I didn't look at the link your first comment until after I've posted the answer; now I see that my answer is in fact a duplicate of the answer by Jorge Fernández in that topic.
– user437309
Aug 6 at 21:29
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
List all polynomials in $mathbb F_2[x]$ that are minimal polynomials of elements from $mathbb F_16$.
Since minimal polynomials are irreducible, this problem just asks to list irreducible polynomials of certain degrees over $mathbb F_2$. But I have a hard time realizing what degrees I should consider. Does it have to do with the fact about the orders of subfields of finite fields? I'm not sure how to apply it.
abstract-algebra polynomials field-theory finite-fields irreducible-polynomials
asked Aug 6 at 1:31
user437309
556212
List all polynomials in $mathbb F_2[x]$ that are minimal polynomials of elements from $mathbb F_16$.
Since minimal polynomials are irreducible, this problem just asks to list irreducible polynomials of certain degrees over $mathbb F_2$. But I have a hard time realizing what degrees I should consider. Does it have to do with the fact about the orders of subfields of finite fields? I'm not sure how to apply it.
abstract-algebra polynomials field-theory finite-fields irreducible-polynomials
asked Aug 6 at 1:31
user437309
556212
asked Aug 6 at 1:31
user437309
556212
asked Aug 6 at 1:31
user437309
556212
asked Aug 6 at 1:31
user437309
556212
556212
4
All elements of $mathbbF_16$ are roots of $x^16-x$. Therefore, all minimal polynomials of elements of $mathbbF_16$ are irreducible factors of $x^16-x$.
– user580373
Aug 6 at 1:48
3
Don’t forget that the degree of the minimal polynomial for $alpha$ is the degree of $Bbb F_2(alpha)$ over $Bbb F_2$. So this degree can only be $1$, $2$, or $4$. Thus aside from $x$ and $x+1$, the only irreducible linears, and $x^2+x+1$, the only irreducible quadratic, you need to find the three irreducible quartics. This is not hard, when you realize that the constant term must be $1$ and there must be an odd number of monomials.
– Lubin
Aug 6 at 2:02
After Lubin's comment the question is reduced to this. Opinions differ whether that is now a duplicate or not. I would say it is, but I don't want to be the first to cast a vote, because I have dupehammer powers here.
– Jyrki Lahtonen
Aug 6 at 7:31
Of course, spiralstotheleft's comment reduces the question to this instead. May be you could post an answer based on those? That way you get a bit more feedback on your understanding this theme, and we get this question out of the unanswered pile.
– Jyrki Lahtonen
Aug 6 at 7:32
@JyrkiLahtonen I've posted an answer below. I didn't look at the link your first comment until after I've posted the answer; now I see that my answer is in fact a duplicate of the answer by Jorge Fernández in that topic.
– user437309
Aug 6 at 21:29
add a comment |Â
4
All elements of $mathbbF_16$ are roots of $x^16-x$. Therefore, all minimal polynomials of elements of $mathbbF_16$ are irreducible factors of $x^16-x$.
– user580373
Aug 6 at 1:48
3
Don’t forget that the degree of the minimal polynomial for $alpha$ is the degree of $Bbb F_2(alpha)$ over $Bbb F_2$. So this degree can only be $1$, $2$, or $4$. Thus aside from $x$ and $x+1$, the only irreducible linears, and $x^2+x+1$, the only irreducible quadratic, you need to find the three irreducible quartics. This is not hard, when you realize that the constant term must be $1$ and there must be an odd number of monomials.
– Lubin
Aug 6 at 2:02
After Lubin's comment the question is reduced to this. Opinions differ whether that is now a duplicate or not. I would say it is, but I don't want to be the first to cast a vote, because I have dupehammer powers here.
– Jyrki Lahtonen
Aug 6 at 7:31
Of course, spiralstotheleft's comment reduces the question to this instead. May be you could post an answer based on those? That way you get a bit more feedback on your understanding this theme, and we get this question out of the unanswered pile.
– Jyrki Lahtonen
Aug 6 at 7:32
@JyrkiLahtonen I've posted an answer below. I didn't look at the link your first comment until after I've posted the answer; now I see that my answer is in fact a duplicate of the answer by Jorge Fernández in that topic.
– user437309
Aug 6 at 21:29
4
4
All elements of $mathbbF_16$ are roots of $x^16-x$. Therefore, all minimal polynomials of elements of $mathbbF_16$ are irreducible factors of $x^16-x$.
– user580373
Aug 6 at 1:48
All elements of $mathbbF_16$ are roots of $x^16-x$. Therefore, all minimal polynomials of elements of $mathbbF_16$ are irreducible factors of $x^16-x$.
– user580373
Aug 6 at 1:48
3
3
Don’t forget that the degree of the minimal polynomial for $alpha$ is the degree of $Bbb F_2(alpha)$ over $Bbb F_2$. So this degree can only be $1$, $2$, or $4$. Thus aside from $x$ and $x+1$, the only irreducible linears, and $x^2+x+1$, the only irreducible quadratic, you need to find the three irreducible quartics. This is not hard, when you realize that the constant term must be $1$ and there must be an odd number of monomials.
– Lubin
Aug 6 at 2:02
Don’t forget that the degree of the minimal polynomial for $alpha$ is the degree of $Bbb F_2(alpha)$ over $Bbb F_2$. So this degree can only be $1$, $2$, or $4$. Thus aside from $x$ and $x+1$, the only irreducible linears, and $x^2+x+1$, the only irreducible quadratic, you need to find the three irreducible quartics. This is not hard, when you realize that the constant term must be $1$ and there must be an odd number of monomials.
– Lubin
Aug 6 at 2:02
After Lubin's comment the question is reduced to this. Opinions differ whether that is now a duplicate or not. I would say it is, but I don't want to be the first to cast a vote, because I have dupehammer powers here.
– Jyrki Lahtonen
Aug 6 at 7:31
After Lubin's comment the question is reduced to this. Opinions differ whether that is now a duplicate or not. I would say it is, but I don't want to be the first to cast a vote, because I have dupehammer powers here.
– Jyrki Lahtonen
Aug 6 at 7:31
Of course, spiralstotheleft's comment reduces the question to this instead. May be you could post an answer based on those? That way you get a bit more feedback on your understanding this theme, and we get this question out of the unanswered pile.
– Jyrki Lahtonen
Aug 6 at 7:32
Of course, spiralstotheleft's comment reduces the question to this instead. May be you could post an answer based on those? That way you get a bit more feedback on your understanding this theme, and we get this question out of the unanswered pile.
– Jyrki Lahtonen
Aug 6 at 7:32
@JyrkiLahtonen I've posted an answer below. I didn't look at the link your first comment until after I've posted the answer; now I see that my answer is in fact a duplicate of the answer by Jorge Fernández in that topic.
– user437309
Aug 6 at 21:29
@JyrkiLahtonen I've posted an answer below. I didn't look at the link your first comment until after I've posted the answer; now I see that my answer is in fact a duplicate of the answer by Jorge Fernández in that topic.
– user437309
Aug 6 at 21:29
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
The elements of $mathbb F_2^4$ are the roots of $x^2^4-x$. By the general theory, the irreducible factors of $x^p^r-x$ over $mathbb F_p$ are the irreducible polynomials in $mathbb F_p[x]$ whose degrees divide $r$. Thus we need to list all irreducible polynomials over $mathbb F_2$ of degrees $1,2,4$.
Degree $1$: $x,x+1$.
Degree $2$: $x^2+x+1$ (the other three polynomials have roots in the field).
Degree $4$: write out all polynomials of degree $4$ (there are $16 $ of them) and cross out those having roots. The remaining polynomials are $$x^4+x^3+x^2+x+1,x^4+x^2+1,x^4+x+1,x^4+x^3+1.$$ We need to delete from this list the polynomials that have an irreducible factor of degree $2$. Since the only irreducible polynomial of degree $2$ is $x^2+x+1$ and $(x^2+x+1)^2=x^4+x^2+1$, the three polynomials $x^4+x^3+x^2+x+1,x^4+x+1,x^4+x^3+1$ form a complete list of degree $4$ irreducible polynomials.
answered Aug 6 at 21:29
user437309
556212
That's all there is to it!
– Jyrki Lahtonen
Aug 7 at 4:51
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
The elements of $mathbb F_2^4$ are the roots of $x^2^4-x$. By the general theory, the irreducible factors of $x^p^r-x$ over $mathbb F_p$ are the irreducible polynomials in $mathbb F_p[x]$ whose degrees divide $r$. Thus we need to list all irreducible polynomials over $mathbb F_2$ of degrees $1,2,4$.
Degree $1$: $x,x+1$.
Degree $2$: $x^2+x+1$ (the other three polynomials have roots in the field).
Degree $4$: write out all polynomials of degree $4$ (there are $16 $ of them) and cross out those having roots. The remaining polynomials are $$x^4+x^3+x^2+x+1,x^4+x^2+1,x^4+x+1,x^4+x^3+1.$$ We need to delete from this list the polynomials that have an irreducible factor of degree $2$. Since the only irreducible polynomial of degree $2$ is $x^2+x+1$ and $(x^2+x+1)^2=x^4+x^2+1$, the three polynomials $x^4+x^3+x^2+x+1,x^4+x+1,x^4+x^3+1$ form a complete list of degree $4$ irreducible polynomials.
answered Aug 6 at 21:29
user437309
556212
That's all there is to it!
– Jyrki Lahtonen
Aug 7 at 4:51
add a comment |Â
up vote
1
down vote
accepted
The elements of $mathbb F_2^4$ are the roots of $x^2^4-x$. By the general theory, the irreducible factors of $x^p^r-x$ over $mathbb F_p$ are the irreducible polynomials in $mathbb F_p[x]$ whose degrees divide $r$. Thus we need to list all irreducible polynomials over $mathbb F_2$ of degrees $1,2,4$.
Degree $1$: $x,x+1$.
Degree $2$: $x^2+x+1$ (the other three polynomials have roots in the field).
Degree $4$: write out all polynomials of degree $4$ (there are $16 $ of them) and cross out those having roots. The remaining polynomials are $$x^4+x^3+x^2+x+1,x^4+x^2+1,x^4+x+1,x^4+x^3+1.$$ We need to delete from this list the polynomials that have an irreducible factor of degree $2$. Since the only irreducible polynomial of degree $2$ is $x^2+x+1$ and $(x^2+x+1)^2=x^4+x^2+1$, the three polynomials $x^4+x^3+x^2+x+1,x^4+x+1,x^4+x^3+1$ form a complete list of degree $4$ irreducible polynomials.
answered Aug 6 at 21:29
user437309
556212
That's all there is to it!
– Jyrki Lahtonen
Aug 7 at 4:51
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
The elements of $mathbb F_2^4$ are the roots of $x^2^4-x$. By the general theory, the irreducible factors of $x^p^r-x$ over $mathbb F_p$ are the irreducible polynomials in $mathbb F_p[x]$ whose degrees divide $r$. Thus we need to list all irreducible polynomials over $mathbb F_2$ of degrees $1,2,4$.
Degree $1$: $x,x+1$.
Degree $2$: $x^2+x+1$ (the other three polynomials have roots in the field).
Degree $4$: write out all polynomials of degree $4$ (there are $16 $ of them) and cross out those having roots. The remaining polynomials are $$x^4+x^3+x^2+x+1,x^4+x^2+1,x^4+x+1,x^4+x^3+1.$$ We need to delete from this list the polynomials that have an irreducible factor of degree $2$. Since the only irreducible polynomial of degree $2$ is $x^2+x+1$ and $(x^2+x+1)^2=x^4+x^2+1$, the three polynomials $x^4+x^3+x^2+x+1,x^4+x+1,x^4+x^3+1$ form a complete list of degree $4$ irreducible polynomials.
answered Aug 6 at 21:29
user437309
556212
The elements of $mathbb F_2^4$ are the roots of $x^2^4-x$. By the general theory, the irreducible factors of $x^p^r-x$ over $mathbb F_p$ are the irreducible polynomials in $mathbb F_p[x]$ whose degrees divide $r$. Thus we need to list all irreducible polynomials over $mathbb F_2$ of degrees $1,2,4$.
Degree $1$: $x,x+1$.
Degree $2$: $x^2+x+1$ (the other three polynomials have roots in the field).
Degree $4$: write out all polynomials of degree $4$ (there are $16 $ of them) and cross out those having roots. The remaining polynomials are $$x^4+x^3+x^2+x+1,x^4+x^2+1,x^4+x+1,x^4+x^3+1.$$ We need to delete from this list the polynomials that have an irreducible factor of degree $2$. Since the only irreducible polynomial of degree $2$ is $x^2+x+1$ and $(x^2+x+1)^2=x^4+x^2+1$, the three polynomials $x^4+x^3+x^2+x+1,x^4+x+1,x^4+x^3+1$ form a complete list of degree $4$ irreducible polynomials.
answered Aug 6 at 21:29
user437309
556212
answered Aug 6 at 21:29
user437309
556212
answered Aug 6 at 21:29
user437309
556212
answered Aug 6 at 21:29
user437309
556212
556212
That's all there is to it!
– Jyrki Lahtonen
Aug 7 at 4:51
add a comment |Â
That's all there is to it!
– Jyrki Lahtonen
Aug 7 at 4:51
That's all there is to it!
– Jyrki Lahtonen
Aug 7 at 4:51
That's all there is to it!
– Jyrki Lahtonen
Aug 7 at 4:51
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873509%2fminimal-polynomials-of-elements-in-mathbb-f-16%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
4
All elements of $mathbbF_16$ are roots of $x^16-x$. Therefore, all minimal polynomials of elements of $mathbbF_16$ are irreducible factors of $x^16-x$.
– user580373
Aug 6 at 1:48
3
Don’t forget that the degree of the minimal polynomial for $alpha$ is the degree of $Bbb F_2(alpha)$ over $Bbb F_2$. So this degree can only be $1$, $2$, or $4$. Thus aside from $x$ and $x+1$, the only irreducible linears, and $x^2+x+1$, the only irreducible quadratic, you need to find the three irreducible quartics. This is not hard, when you realize that the constant term must be $1$ and there must be an odd number of monomials.
– Lubin
Aug 6 at 2:02
After Lubin's comment the question is reduced to this. Opinions differ whether that is now a duplicate or not. I would say it is, but I don't want to be the first to cast a vote, because I have dupehammer powers here.
– Jyrki Lahtonen
Aug 6 at 7:31
Of course, spiralstotheleft's comment reduces the question to this instead. May be you could post an answer based on those? That way you get a bit more feedback on your understanding this theme, and we get this question out of the unanswered pile.
– Jyrki Lahtonen
Aug 6 at 7:32
@JyrkiLahtonen I've posted an answer below. I didn't look at the link your first comment until after I've posted the answer; now I see that my answer is in fact a duplicate of the answer by Jorge Fernández in that topic.
– user437309
Aug 6 at 21:29