How to construct finite fields of any prime power order?
$begingroup$
For a prime $p$, I know that $mathbb Z_p$ is a field. To construct a field with four elements, I know I can just take $frac{mathbb Z_2[x]}{(x^2+x+1)}$. Similarly, to construct a field of order $p^n$, do I just need to take $mathbb Z_p[x]$ and quotient out an irreducible polynomial of degree $n$? Is there any pattern to these irreducible polynomials, or do I just have to find one by brute force?
ring-theory finite-fields
edited Jan 4 '14 at 16:34
Michael Hardy
1
asked Jan 4 '14 at 16:13
NishantNishant
5,84721132
$endgroup$
add a comment |
$begingroup$
For a prime $p$, I know that $mathbb Z_p$ is a field. To construct a field with four elements, I know I can just take $frac{mathbb Z_2[x]}{(x^2+x+1)}$. Similarly, to construct a field of order $p^n$, do I just need to take $mathbb Z_p[x]$ and quotient out an irreducible polynomial of degree $n$? Is there any pattern to these irreducible polynomials, or do I just have to find one by brute force?
ring-theory finite-fields
edited Jan 4 '14 at 16:34
Michael Hardy
1
asked Jan 4 '14 at 16:13
NishantNishant
5,84721132
$endgroup$
$begingroup$
This reference might be useful en.wikipedia.org/wiki/Conway_polynomial_(finite_fields)
$endgroup$
– Andreas Caranti
Jan 4 '14 at 16:24
1
$begingroup$
Pari has a function (ffinit) which given $p$ and $n$ outputs an irreducible polynomial of degree $n$ over $mathbf{F}_p$. The documentation says it uses "a fast variant of Adleman and Lenstra's algorithm", which I suppose refers to math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf
$endgroup$
– fkraiem
Jan 4 '14 at 16:31
add a comment |
$begingroup$
For a prime $p$, I know that $mathbb Z_p$ is a field. To construct a field with four elements, I know I can just take $frac{mathbb Z_2[x]}{(x^2+x+1)}$. Similarly, to construct a field of order $p^n$, do I just need to take $mathbb Z_p[x]$ and quotient out an irreducible polynomial of degree $n$? Is there any pattern to these irreducible polynomials, or do I just have to find one by brute force?
ring-theory finite-fields
edited Jan 4 '14 at 16:34
Michael Hardy
1
asked Jan 4 '14 at 16:13
NishantNishant
5,84721132
$endgroup$
For a prime $p$, I know that $mathbb Z_p$ is a field. To construct a field with four elements, I know I can just take $frac{mathbb Z_2[x]}{(x^2+x+1)}$. Similarly, to construct a field of order $p^n$, do I just need to take $mathbb Z_p[x]$ and quotient out an irreducible polynomial of degree $n$? Is there any pattern to these irreducible polynomials, or do I just have to find one by brute force?
ring-theory finite-fields
ring-theory finite-fields
edited Jan 4 '14 at 16:34
Michael Hardy
1
asked Jan 4 '14 at 16:13
NishantNishant
5,84721132
edited Jan 4 '14 at 16:34
Michael Hardy
1
asked Jan 4 '14 at 16:13
NishantNishant
5,84721132
edited Jan 4 '14 at 16:34
Michael Hardy
1
edited Jan 4 '14 at 16:34
Michael Hardy
1
edited Jan 4 '14 at 16:34
Michael Hardy
1
1
asked Jan 4 '14 at 16:13
NishantNishant
5,84721132
asked Jan 4 '14 at 16:13
NishantNishant
5,84721132
asked Jan 4 '14 at 16:13
NishantNishant
5,84721132
5,84721132
$begingroup$
This reference might be useful en.wikipedia.org/wiki/Conway_polynomial_(finite_fields)
$endgroup$
– Andreas Caranti
Jan 4 '14 at 16:24
1
$begingroup$
Pari has a function (ffinit) which given $p$ and $n$ outputs an irreducible polynomial of degree $n$ over $mathbf{F}_p$. The documentation says it uses "a fast variant of Adleman and Lenstra's algorithm", which I suppose refers to math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf
$endgroup$
– fkraiem
Jan 4 '14 at 16:31
add a comment |
$begingroup$
This reference might be useful en.wikipedia.org/wiki/Conway_polynomial_(finite_fields)
$endgroup$
– Andreas Caranti
Jan 4 '14 at 16:24
1
$begingroup$
Pari has a function (ffinit) which given $p$ and $n$ outputs an irreducible polynomial of degree $n$ over $mathbf{F}_p$. The documentation says it uses "a fast variant of Adleman and Lenstra's algorithm", which I suppose refers to math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf
$endgroup$
– fkraiem
Jan 4 '14 at 16:31
$begingroup$
This reference might be useful en.wikipedia.org/wiki/Conway_polynomial_(finite_fields)
$endgroup$
– Andreas Caranti
Jan 4 '14 at 16:24
$begingroup$
This reference might be useful en.wikipedia.org/wiki/Conway_polynomial_(finite_fields)
$endgroup$
– Andreas Caranti
Jan 4 '14 at 16:24
1
1
$begingroup$
Pari has a function (ffinit) which given $p$ and $n$ outputs an irreducible polynomial of degree $n$ over $mathbf{F}_p$. The documentation says it uses "a fast variant of Adleman and Lenstra's algorithm", which I suppose refers to math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf
$endgroup$
– fkraiem
Jan 4 '14 at 16:31
$begingroup$
Pari has a function (ffinit) which given $p$ and $n$ outputs an irreducible polynomial of degree $n$ over $mathbf{F}_p$. The documentation says it uses "a fast variant of Adleman and Lenstra's algorithm", which I suppose refers to math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf
$endgroup$
– fkraiem
Jan 4 '14 at 16:31
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
I don't think there is any general procedure to find an irreducible polynomial of degree $n$ over $mathbb{Z}_p$. However, any such polynomial $p(x)$ works, i.e. it will produce a field $mathbb{Z}[x]/(p(x))$ of order $p^n$.
answered Jan 4 '14 at 16:18
UlrikUlrik
2,041917
$endgroup$
$begingroup$
Also, why is is that this always gives fields isomorphic to each other?
$endgroup$
– Nishant
Jan 4 '14 at 16:19
6
$begingroup$
A way to prove this is to show that any field of $p^n$ elements is a splitting field of the polynomial $x^{p^n} - x in mathbb{Z}_p[x]$, and then use that any two splitting fields for the same polynomial are isomorphic.
$endgroup$
– Ulrik
Jan 4 '14 at 16:22
add a comment |
$begingroup$
If you want to "construct" such fields, when $n$ is a power of 2, and $p neq 2$, you can do the following:
- Start with a field with $p$ elements.
- Such a field will always have an element that does not have a square roots. Let it be $Q$.
- Construct a field with $p^2$ elements with each element given by $a + sqrt{Q} b$ where $a$ and $b$ are elements in the field
Above procedure can be repeated as many times as needed. If you write computer programs, or you want a concrete representation that does not involve square roots then you can set up an isomorphism between the new field and a subset of $2times 2$ matrices in the original field as
$$
a + sqrt{Q} b leftrightarrow begin{pmatrix} a & b \ Q^2 b & a end{pmatrix} $$
This will allow you to do all your work in the base field (also very useful if you want to write computer programs and don't mind being a bit inefficient).
answered Jan 4 '14 at 16:39
user44197user44197
9,0281117
$endgroup$
add a comment |
$begingroup$
hey there yes for constructing a field with $p^k$ elements where $p$ is a prime number and $k$ is a natural number you can take any $f(x)$ in $mathbb{Z}_p[x]$ which is irreducible of degree $k$ then using that theorem you have a field with $p^k$ elements
edited Jan 11 at 14:33
pie314271
2,129819
answered Jan 11 at 9:27
Parmida GranfarParmida Granfar
112
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f627073%2fhow-to-construct-finite-fields-of-any-prime-power-order%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I don't think there is any general procedure to find an irreducible polynomial of degree $n$ over $mathbb{Z}_p$. However, any such polynomial $p(x)$ works, i.e. it will produce a field $mathbb{Z}[x]/(p(x))$ of order $p^n$.
answered Jan 4 '14 at 16:18
UlrikUlrik
2,041917
$endgroup$
$begingroup$
Also, why is is that this always gives fields isomorphic to each other?
$endgroup$
– Nishant
Jan 4 '14 at 16:19
6
$begingroup$
A way to prove this is to show that any field of $p^n$ elements is a splitting field of the polynomial $x^{p^n} - x in mathbb{Z}_p[x]$, and then use that any two splitting fields for the same polynomial are isomorphic.
$endgroup$
– Ulrik
Jan 4 '14 at 16:22
add a comment |
$begingroup$
I don't think there is any general procedure to find an irreducible polynomial of degree $n$ over $mathbb{Z}_p$. However, any such polynomial $p(x)$ works, i.e. it will produce a field $mathbb{Z}[x]/(p(x))$ of order $p^n$.
answered Jan 4 '14 at 16:18
UlrikUlrik
2,041917
$endgroup$
$begingroup$
Also, why is is that this always gives fields isomorphic to each other?
$endgroup$
– Nishant
Jan 4 '14 at 16:19
6
$begingroup$
A way to prove this is to show that any field of $p^n$ elements is a splitting field of the polynomial $x^{p^n} - x in mathbb{Z}_p[x]$, and then use that any two splitting fields for the same polynomial are isomorphic.
$endgroup$
– Ulrik
Jan 4 '14 at 16:22
add a comment |
$begingroup$
I don't think there is any general procedure to find an irreducible polynomial of degree $n$ over $mathbb{Z}_p$. However, any such polynomial $p(x)$ works, i.e. it will produce a field $mathbb{Z}[x]/(p(x))$ of order $p^n$.
answered Jan 4 '14 at 16:18
UlrikUlrik
2,041917
$endgroup$
I don't think there is any general procedure to find an irreducible polynomial of degree $n$ over $mathbb{Z}_p$. However, any such polynomial $p(x)$ works, i.e. it will produce a field $mathbb{Z}[x]/(p(x))$ of order $p^n$.
answered Jan 4 '14 at 16:18
UlrikUlrik
2,041917
answered Jan 4 '14 at 16:18
UlrikUlrik
2,041917
answered Jan 4 '14 at 16:18
UlrikUlrik
2,041917
answered Jan 4 '14 at 16:18
UlrikUlrik
2,041917
2,041917
$begingroup$
Also, why is is that this always gives fields isomorphic to each other?
$endgroup$
– Nishant
Jan 4 '14 at 16:19
6
$begingroup$
A way to prove this is to show that any field of $p^n$ elements is a splitting field of the polynomial $x^{p^n} - x in mathbb{Z}_p[x]$, and then use that any two splitting fields for the same polynomial are isomorphic.
$endgroup$
– Ulrik
Jan 4 '14 at 16:22
add a comment |
$begingroup$
Also, why is is that this always gives fields isomorphic to each other?
$endgroup$
– Nishant
Jan 4 '14 at 16:19
6
$begingroup$
A way to prove this is to show that any field of $p^n$ elements is a splitting field of the polynomial $x^{p^n} - x in mathbb{Z}_p[x]$, and then use that any two splitting fields for the same polynomial are isomorphic.
$endgroup$
– Ulrik
Jan 4 '14 at 16:22
$begingroup$
Also, why is is that this always gives fields isomorphic to each other?
$endgroup$
– Nishant
Jan 4 '14 at 16:19
$begingroup$
Also, why is is that this always gives fields isomorphic to each other?
$endgroup$
– Nishant
Jan 4 '14 at 16:19
6
6
$begingroup$
A way to prove this is to show that any field of $p^n$ elements is a splitting field of the polynomial $x^{p^n} - x in mathbb{Z}_p[x]$, and then use that any two splitting fields for the same polynomial are isomorphic.
$endgroup$
– Ulrik
Jan 4 '14 at 16:22
$begingroup$
A way to prove this is to show that any field of $p^n$ elements is a splitting field of the polynomial $x^{p^n} - x in mathbb{Z}_p[x]$, and then use that any two splitting fields for the same polynomial are isomorphic.
$endgroup$
– Ulrik
Jan 4 '14 at 16:22
add a comment |
$begingroup$
If you want to "construct" such fields, when $n$ is a power of 2, and $p neq 2$, you can do the following:
- Start with a field with $p$ elements.
- Such a field will always have an element that does not have a square roots. Let it be $Q$.
- Construct a field with $p^2$ elements with each element given by $a + sqrt{Q} b$ where $a$ and $b$ are elements in the field
Above procedure can be repeated as many times as needed. If you write computer programs, or you want a concrete representation that does not involve square roots then you can set up an isomorphism between the new field and a subset of $2times 2$ matrices in the original field as
$$
a + sqrt{Q} b leftrightarrow begin{pmatrix} a & b \ Q^2 b & a end{pmatrix} $$
This will allow you to do all your work in the base field (also very useful if you want to write computer programs and don't mind being a bit inefficient).
answered Jan 4 '14 at 16:39
user44197user44197
9,0281117
$endgroup$
add a comment |
$begingroup$
If you want to "construct" such fields, when $n$ is a power of 2, and $p neq 2$, you can do the following:
- Start with a field with $p$ elements.
- Such a field will always have an element that does not have a square roots. Let it be $Q$.
- Construct a field with $p^2$ elements with each element given by $a + sqrt{Q} b$ where $a$ and $b$ are elements in the field
Above procedure can be repeated as many times as needed. If you write computer programs, or you want a concrete representation that does not involve square roots then you can set up an isomorphism between the new field and a subset of $2times 2$ matrices in the original field as
$$
a + sqrt{Q} b leftrightarrow begin{pmatrix} a & b \ Q^2 b & a end{pmatrix} $$
This will allow you to do all your work in the base field (also very useful if you want to write computer programs and don't mind being a bit inefficient).
answered Jan 4 '14 at 16:39
user44197user44197
9,0281117
$endgroup$
add a comment |
$begingroup$
If you want to "construct" such fields, when $n$ is a power of 2, and $p neq 2$, you can do the following:
- Start with a field with $p$ elements.
- Such a field will always have an element that does not have a square roots. Let it be $Q$.
- Construct a field with $p^2$ elements with each element given by $a + sqrt{Q} b$ where $a$ and $b$ are elements in the field
Above procedure can be repeated as many times as needed. If you write computer programs, or you want a concrete representation that does not involve square roots then you can set up an isomorphism between the new field and a subset of $2times 2$ matrices in the original field as
$$
a + sqrt{Q} b leftrightarrow begin{pmatrix} a & b \ Q^2 b & a end{pmatrix} $$
This will allow you to do all your work in the base field (also very useful if you want to write computer programs and don't mind being a bit inefficient).
answered Jan 4 '14 at 16:39
user44197user44197
9,0281117
$endgroup$
If you want to "construct" such fields, when $n$ is a power of 2, and $p neq 2$, you can do the following:
- Start with a field with $p$ elements.
- Such a field will always have an element that does not have a square roots. Let it be $Q$.
- Construct a field with $p^2$ elements with each element given by $a + sqrt{Q} b$ where $a$ and $b$ are elements in the field
Above procedure can be repeated as many times as needed. If you write computer programs, or you want a concrete representation that does not involve square roots then you can set up an isomorphism between the new field and a subset of $2times 2$ matrices in the original field as
$$
a + sqrt{Q} b leftrightarrow begin{pmatrix} a & b \ Q^2 b & a end{pmatrix} $$
This will allow you to do all your work in the base field (also very useful if you want to write computer programs and don't mind being a bit inefficient).
answered Jan 4 '14 at 16:39
user44197user44197
9,0281117
answered Jan 4 '14 at 16:39
user44197user44197
9,0281117
answered Jan 4 '14 at 16:39
user44197user44197
9,0281117
answered Jan 4 '14 at 16:39
user44197user44197
9,0281117
9,0281117
add a comment |
add a comment |
$begingroup$
hey there yes for constructing a field with $p^k$ elements where $p$ is a prime number and $k$ is a natural number you can take any $f(x)$ in $mathbb{Z}_p[x]$ which is irreducible of degree $k$ then using that theorem you have a field with $p^k$ elements
edited Jan 11 at 14:33
pie314271
2,129819
answered Jan 11 at 9:27
Parmida GranfarParmida Granfar
112
$endgroup$
add a comment |
$begingroup$
hey there yes for constructing a field with $p^k$ elements where $p$ is a prime number and $k$ is a natural number you can take any $f(x)$ in $mathbb{Z}_p[x]$ which is irreducible of degree $k$ then using that theorem you have a field with $p^k$ elements
edited Jan 11 at 14:33
pie314271
2,129819
answered Jan 11 at 9:27
Parmida GranfarParmida Granfar
112
$endgroup$
add a comment |
$begingroup$
hey there yes for constructing a field with $p^k$ elements where $p$ is a prime number and $k$ is a natural number you can take any $f(x)$ in $mathbb{Z}_p[x]$ which is irreducible of degree $k$ then using that theorem you have a field with $p^k$ elements
edited Jan 11 at 14:33
pie314271
2,129819
answered Jan 11 at 9:27
Parmida GranfarParmida Granfar
112
$endgroup$
hey there yes for constructing a field with $p^k$ elements where $p$ is a prime number and $k$ is a natural number you can take any $f(x)$ in $mathbb{Z}_p[x]$ which is irreducible of degree $k$ then using that theorem you have a field with $p^k$ elements
edited Jan 11 at 14:33
pie314271
2,129819
answered Jan 11 at 9:27
Parmida GranfarParmida Granfar
112
edited Jan 11 at 14:33
pie314271
2,129819
edited Jan 11 at 14:33
pie314271
2,129819
edited Jan 11 at 14:33
pie314271
2,129819
2,129819
answered Jan 11 at 9:27
Parmida GranfarParmida Granfar
112
answered Jan 11 at 9:27
Parmida GranfarParmida Granfar
112
answered Jan 11 at 9:27
Parmida GranfarParmida Granfar
112
112
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f627073%2fhow-to-construct-finite-fields-of-any-prime-power-order%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
This reference might be useful en.wikipedia.org/wiki/Conway_polynomial_(finite_fields)
$endgroup$
– Andreas Caranti
Jan 4 '14 at 16:24
1
$begingroup$
Pari has a function (ffinit) which given $p$ and $n$ outputs an irreducible polynomial of degree $n$ over $mathbf{F}_p$. The documentation says it uses "a fast variant of Adleman and Lenstra's algorithm", which I suppose refers to math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf
$endgroup$
– fkraiem
Jan 4 '14 at 16:31