How to construct finite fields of any prime power order?












1












$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







share|cite|improve this question











$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
















1












$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







share|cite|improve this question











$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














1












1








1


1



$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







share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 4 '14 at 16:34









Michael Hardy

1




1










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


















  • $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










3 Answers
3






active

oldest

votes


















1












$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$.






share|cite|improve this answer









$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





















1












$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).






share|cite|improve this answer









$endgroup$





















    1












    $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






    share|cite|improve this answer











    $endgroup$














      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
      });


      }
      });














      draft saved

      draft discarded


















      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









      1












      $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$.






      share|cite|improve this answer









      $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


















      1












      $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$.






      share|cite|improve this answer









      $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
















      1












      1








      1





      $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$.






      share|cite|improve this answer









      $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$.







      share|cite|improve this answer












      share|cite|improve this answer



      share|cite|improve this answer










      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




















      • $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













      1












      $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).






      share|cite|improve this answer









      $endgroup$


















        1












        $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).






        share|cite|improve this answer









        $endgroup$
















          1












          1








          1





          $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).






          share|cite|improve this answer









          $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).







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Jan 4 '14 at 16:39









          user44197user44197

          9,0281117




          9,0281117























              1












              $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






              share|cite|improve this answer











              $endgroup$


















                1












                $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






                share|cite|improve this answer











                $endgroup$
















                  1












                  1








                  1





                  $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






                  share|cite|improve this answer











                  $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







                  share|cite|improve this answer














                  share|cite|improve this answer



                  share|cite|improve this answer








                  edited Jan 11 at 14:33









                  pie314271

                  2,129819




                  2,129819










                  answered Jan 11 at 9:27









                  Parmida GranfarParmida Granfar

                  112




                  112






























                      draft saved

                      draft discarded




















































                      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.




                      draft saved


                      draft discarded














                      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





















































                      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







                      -

                      Popular posts from this blog

                      Bressuire

                      Image
                      .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid ...
                      Read more

                      Cabo Verde

                      Image
                        Nota: Cabo-verdiano redireciona para este artigo. Para a língua falada em Cabo Verde, veja crioulo cabo-verdiano. Para outros significados, veja Cabo Verde (desambiguação). Coordenadas: 14° 55' N 23° 31' O Cabo Verde República de Cabo Verde Bandeira Brasão de Armas Lema: Unidade, Trabalho, Progresso Hino nacional: Cântico da Liberdade Gentílico: cabo-verdiano [ 1 ] Capital Praia 14° 55' N 23° 31' O Cidade mais populosa Praia Língua oficial Português Governo República unitária semipresidencialista [ 2 ]  - Presidente Jorge Carlos Fonseca  - Primeiro-ministro Ulisses Correia e Silva História    - Descoberta 1460   - Independência 00 • de Portugal 5 de Julho de 1975   - Multipartidarismo 13 de Janeiro de 1990  Área    - Total 4 033 km² (146.º)  - Água (%) 0,08 População    - Estimativa para 2017 560 899 [ 3 ] hab. (173.º) ...
                      Read more

                      Gyllenstierna

                      Image
                      .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid ...
                      Read more