Irreducible polynomials of degree greater than 4 over finite fields












3














I want to build a field with p^n elements. I know that this can be done by finding a irreducible (on Z_p) polynomial f of degree n and the result would be the Z_p/f.
My question is finding this irreducible polynomial. I know that if it has degree <= 3, then it's irreducible iff it has no roots. But what if I want to construct a field with 81 = 3^4 elements? How can I find an irreducible polynomial of degree 4?










share|cite|improve this question






















  • For low degrees the best techniques are a bit ad hoc, not unlike Rene Schoof's answer (+1). I have used similar techniques to produce irreducibles of degree 20 and 21 (over $Bbb{Z}_2$) on this site when requested. In general the task takes as much work as producing a prime number of a prescribed size. The tricks based on the algebra of roots of unity as well as splitting fields does simplify this in many occasions.
    – Jyrki Lahtonen
    Jan 2 at 5:39










  • An alternative to Rene Schoof's observation would be to use the fact that $Bbb{F}_{3^4}$ is the smallest extension field containing roots of unity of order sixteen. Those are always roots of the sixteenth cyclotomic polynomial $Phi_{16}=x^8+1$. Over $Bbb{F}_3$ that polynomial factors as $$x^8+1=(x^8+4x^4+4)-4x^4=(x^4+2)^2-(2x^2)^2=(x^4-2x^2+2)(x^4+2x^2+2),$$ so we can deduce right away that the quartics above are irreducible.
    – Jyrki Lahtonen
    Jan 2 at 5:45












  • Hmm. Actually I don't think that this task would be asymptotically as arduous as that of locating prime numbers. But you need methods other than the Sieve of Eratosthenes (which is what Ethan Bolker's answer is suggesting).
    – Jyrki Lahtonen
    Jan 2 at 5:48
















3














I want to build a field with p^n elements. I know that this can be done by finding a irreducible (on Z_p) polynomial f of degree n and the result would be the Z_p/f.
My question is finding this irreducible polynomial. I know that if it has degree <= 3, then it's irreducible iff it has no roots. But what if I want to construct a field with 81 = 3^4 elements? How can I find an irreducible polynomial of degree 4?










share|cite|improve this question






















  • For low degrees the best techniques are a bit ad hoc, not unlike Rene Schoof's answer (+1). I have used similar techniques to produce irreducibles of degree 20 and 21 (over $Bbb{Z}_2$) on this site when requested. In general the task takes as much work as producing a prime number of a prescribed size. The tricks based on the algebra of roots of unity as well as splitting fields does simplify this in many occasions.
    – Jyrki Lahtonen
    Jan 2 at 5:39










  • An alternative to Rene Schoof's observation would be to use the fact that $Bbb{F}_{3^4}$ is the smallest extension field containing roots of unity of order sixteen. Those are always roots of the sixteenth cyclotomic polynomial $Phi_{16}=x^8+1$. Over $Bbb{F}_3$ that polynomial factors as $$x^8+1=(x^8+4x^4+4)-4x^4=(x^4+2)^2-(2x^2)^2=(x^4-2x^2+2)(x^4+2x^2+2),$$ so we can deduce right away that the quartics above are irreducible.
    – Jyrki Lahtonen
    Jan 2 at 5:45












  • Hmm. Actually I don't think that this task would be asymptotically as arduous as that of locating prime numbers. But you need methods other than the Sieve of Eratosthenes (which is what Ethan Bolker's answer is suggesting).
    – Jyrki Lahtonen
    Jan 2 at 5:48














3












3








3







I want to build a field with p^n elements. I know that this can be done by finding a irreducible (on Z_p) polynomial f of degree n and the result would be the Z_p/f.
My question is finding this irreducible polynomial. I know that if it has degree <= 3, then it's irreducible iff it has no roots. But what if I want to construct a field with 81 = 3^4 elements? How can I find an irreducible polynomial of degree 4?










share|cite|improve this question













I want to build a field with p^n elements. I know that this can be done by finding a irreducible (on Z_p) polynomial f of degree n and the result would be the Z_p/f.
My question is finding this irreducible polynomial. I know that if it has degree <= 3, then it's irreducible iff it has no roots. But what if I want to construct a field with 81 = 3^4 elements? How can I find an irreducible polynomial of degree 4?







number-theory polynomials finite-fields irreducible-polynomials






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Jan 1 at 17:27









J. DionisioJ. Dionisio

9511




9511












  • For low degrees the best techniques are a bit ad hoc, not unlike Rene Schoof's answer (+1). I have used similar techniques to produce irreducibles of degree 20 and 21 (over $Bbb{Z}_2$) on this site when requested. In general the task takes as much work as producing a prime number of a prescribed size. The tricks based on the algebra of roots of unity as well as splitting fields does simplify this in many occasions.
    – Jyrki Lahtonen
    Jan 2 at 5:39










  • An alternative to Rene Schoof's observation would be to use the fact that $Bbb{F}_{3^4}$ is the smallest extension field containing roots of unity of order sixteen. Those are always roots of the sixteenth cyclotomic polynomial $Phi_{16}=x^8+1$. Over $Bbb{F}_3$ that polynomial factors as $$x^8+1=(x^8+4x^4+4)-4x^4=(x^4+2)^2-(2x^2)^2=(x^4-2x^2+2)(x^4+2x^2+2),$$ so we can deduce right away that the quartics above are irreducible.
    – Jyrki Lahtonen
    Jan 2 at 5:45












  • Hmm. Actually I don't think that this task would be asymptotically as arduous as that of locating prime numbers. But you need methods other than the Sieve of Eratosthenes (which is what Ethan Bolker's answer is suggesting).
    – Jyrki Lahtonen
    Jan 2 at 5:48


















  • For low degrees the best techniques are a bit ad hoc, not unlike Rene Schoof's answer (+1). I have used similar techniques to produce irreducibles of degree 20 and 21 (over $Bbb{Z}_2$) on this site when requested. In general the task takes as much work as producing a prime number of a prescribed size. The tricks based on the algebra of roots of unity as well as splitting fields does simplify this in many occasions.
    – Jyrki Lahtonen
    Jan 2 at 5:39










  • An alternative to Rene Schoof's observation would be to use the fact that $Bbb{F}_{3^4}$ is the smallest extension field containing roots of unity of order sixteen. Those are always roots of the sixteenth cyclotomic polynomial $Phi_{16}=x^8+1$. Over $Bbb{F}_3$ that polynomial factors as $$x^8+1=(x^8+4x^4+4)-4x^4=(x^4+2)^2-(2x^2)^2=(x^4-2x^2+2)(x^4+2x^2+2),$$ so we can deduce right away that the quartics above are irreducible.
    – Jyrki Lahtonen
    Jan 2 at 5:45












  • Hmm. Actually I don't think that this task would be asymptotically as arduous as that of locating prime numbers. But you need methods other than the Sieve of Eratosthenes (which is what Ethan Bolker's answer is suggesting).
    – Jyrki Lahtonen
    Jan 2 at 5:48
















For low degrees the best techniques are a bit ad hoc, not unlike Rene Schoof's answer (+1). I have used similar techniques to produce irreducibles of degree 20 and 21 (over $Bbb{Z}_2$) on this site when requested. In general the task takes as much work as producing a prime number of a prescribed size. The tricks based on the algebra of roots of unity as well as splitting fields does simplify this in many occasions.
– Jyrki Lahtonen
Jan 2 at 5:39




For low degrees the best techniques are a bit ad hoc, not unlike Rene Schoof's answer (+1). I have used similar techniques to produce irreducibles of degree 20 and 21 (over $Bbb{Z}_2$) on this site when requested. In general the task takes as much work as producing a prime number of a prescribed size. The tricks based on the algebra of roots of unity as well as splitting fields does simplify this in many occasions.
– Jyrki Lahtonen
Jan 2 at 5:39












An alternative to Rene Schoof's observation would be to use the fact that $Bbb{F}_{3^4}$ is the smallest extension field containing roots of unity of order sixteen. Those are always roots of the sixteenth cyclotomic polynomial $Phi_{16}=x^8+1$. Over $Bbb{F}_3$ that polynomial factors as $$x^8+1=(x^8+4x^4+4)-4x^4=(x^4+2)^2-(2x^2)^2=(x^4-2x^2+2)(x^4+2x^2+2),$$ so we can deduce right away that the quartics above are irreducible.
– Jyrki Lahtonen
Jan 2 at 5:45






An alternative to Rene Schoof's observation would be to use the fact that $Bbb{F}_{3^4}$ is the smallest extension field containing roots of unity of order sixteen. Those are always roots of the sixteenth cyclotomic polynomial $Phi_{16}=x^8+1$. Over $Bbb{F}_3$ that polynomial factors as $$x^8+1=(x^8+4x^4+4)-4x^4=(x^4+2)^2-(2x^2)^2=(x^4-2x^2+2)(x^4+2x^2+2),$$ so we can deduce right away that the quartics above are irreducible.
– Jyrki Lahtonen
Jan 2 at 5:45














Hmm. Actually I don't think that this task would be asymptotically as arduous as that of locating prime numbers. But you need methods other than the Sieve of Eratosthenes (which is what Ethan Bolker's answer is suggesting).
– Jyrki Lahtonen
Jan 2 at 5:48




Hmm. Actually I don't think that this task would be asymptotically as arduous as that of locating prime numbers. But you need methods other than the Sieve of Eratosthenes (which is what Ethan Bolker's answer is suggesting).
– Jyrki Lahtonen
Jan 2 at 5:48










4 Answers
4






active

oldest

votes


















3














Find the irreducible quadratics. Multiply them together. Those fourth degree polynomials won't do. Now try some others at random (or systematically, following a list in some natural order). When you find one with no roots you're done.



This is mildly tedious, but you'll get good at the arithmetic, which may come in handy in other computations in the future.



You can also ask Wolfram alpha to factor polynomials modulo $3$.






share|cite|improve this answer



















  • 1




    Asymptotically, a random monic polynomial of degree $n$ over $Bbb{Z}_p$ is irreducible with probability $1/n$.
    – Jyrki Lahtonen
    Jan 2 at 5:33



















3














Since $3$ is a primitive root modulo $5$, the fifth roots of unity are in ${bf F}_{81}$, but not in a proper subfield. This means that the cyclotomic polynomial $Phi_5(X)=X^4+X^3+X^2+X+1$ is irreducible modulo $3$.






share|cite|improve this answer





























    2














    The elements of $GF(p^n)$ are the zeros of the polynomial $x^{p^n}-x$. This polynomials decomposes into irreducible polynomials of degree $d$ over $GF(p)$ where $d$ divides $n$. It can be shown that this decomposition contains at least one polynomial of degree $n$ which ensures the existence of a finite field with $p^n$ elements. In a CAS you usually have access to such irreducible polynomials.






    share|cite|improve this answer





























      2














      I think the state of the art is Couveignes, J. M., & Lercier, R. (2013). Fast construction of irreducible polynomials over finite fields. Israel Journal of Mathematics, 194(1), 77-105. A preprint is available on arxiv.



      If you want something simpler but better than brute force, you could look at Victor Shoup's work from the 1990s. Shoup, V. (1990). New algorithms for finding irreducible polynomials over finite fields. Mathematics of Computation, 54(189), 435-447 is not the most recent, but is freely available online, unlike the follow-up.



      Obviously both of these also serve as starting points for a literature search.






      share|cite|improve this answer





















      • +1 for the references
        – Jyrki Lahtonen
        Jan 2 at 5:40











      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%2f3058677%2firreducible-polynomials-of-degree-greater-than-4-over-finite-fields%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      4 Answers
      4






      active

      oldest

      votes








      4 Answers
      4






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      3














      Find the irreducible quadratics. Multiply them together. Those fourth degree polynomials won't do. Now try some others at random (or systematically, following a list in some natural order). When you find one with no roots you're done.



      This is mildly tedious, but you'll get good at the arithmetic, which may come in handy in other computations in the future.



      You can also ask Wolfram alpha to factor polynomials modulo $3$.






      share|cite|improve this answer



















      • 1




        Asymptotically, a random monic polynomial of degree $n$ over $Bbb{Z}_p$ is irreducible with probability $1/n$.
        – Jyrki Lahtonen
        Jan 2 at 5:33
















      3














      Find the irreducible quadratics. Multiply them together. Those fourth degree polynomials won't do. Now try some others at random (or systematically, following a list in some natural order). When you find one with no roots you're done.



      This is mildly tedious, but you'll get good at the arithmetic, which may come in handy in other computations in the future.



      You can also ask Wolfram alpha to factor polynomials modulo $3$.






      share|cite|improve this answer



















      • 1




        Asymptotically, a random monic polynomial of degree $n$ over $Bbb{Z}_p$ is irreducible with probability $1/n$.
        – Jyrki Lahtonen
        Jan 2 at 5:33














      3












      3








      3






      Find the irreducible quadratics. Multiply them together. Those fourth degree polynomials won't do. Now try some others at random (or systematically, following a list in some natural order). When you find one with no roots you're done.



      This is mildly tedious, but you'll get good at the arithmetic, which may come in handy in other computations in the future.



      You can also ask Wolfram alpha to factor polynomials modulo $3$.






      share|cite|improve this answer














      Find the irreducible quadratics. Multiply them together. Those fourth degree polynomials won't do. Now try some others at random (or systematically, following a list in some natural order). When you find one with no roots you're done.



      This is mildly tedious, but you'll get good at the arithmetic, which may come in handy in other computations in the future.



      You can also ask Wolfram alpha to factor polynomials modulo $3$.







      share|cite|improve this answer














      share|cite|improve this answer



      share|cite|improve this answer








      edited Jan 1 at 18:45

























      answered Jan 1 at 17:34









      Ethan BolkerEthan Bolker

      42k547110




      42k547110








      • 1




        Asymptotically, a random monic polynomial of degree $n$ over $Bbb{Z}_p$ is irreducible with probability $1/n$.
        – Jyrki Lahtonen
        Jan 2 at 5:33














      • 1




        Asymptotically, a random monic polynomial of degree $n$ over $Bbb{Z}_p$ is irreducible with probability $1/n$.
        – Jyrki Lahtonen
        Jan 2 at 5:33








      1




      1




      Asymptotically, a random monic polynomial of degree $n$ over $Bbb{Z}_p$ is irreducible with probability $1/n$.
      – Jyrki Lahtonen
      Jan 2 at 5:33




      Asymptotically, a random monic polynomial of degree $n$ over $Bbb{Z}_p$ is irreducible with probability $1/n$.
      – Jyrki Lahtonen
      Jan 2 at 5:33











      3














      Since $3$ is a primitive root modulo $5$, the fifth roots of unity are in ${bf F}_{81}$, but not in a proper subfield. This means that the cyclotomic polynomial $Phi_5(X)=X^4+X^3+X^2+X+1$ is irreducible modulo $3$.






      share|cite|improve this answer


























        3














        Since $3$ is a primitive root modulo $5$, the fifth roots of unity are in ${bf F}_{81}$, but not in a proper subfield. This means that the cyclotomic polynomial $Phi_5(X)=X^4+X^3+X^2+X+1$ is irreducible modulo $3$.






        share|cite|improve this answer
























          3












          3








          3






          Since $3$ is a primitive root modulo $5$, the fifth roots of unity are in ${bf F}_{81}$, but not in a proper subfield. This means that the cyclotomic polynomial $Phi_5(X)=X^4+X^3+X^2+X+1$ is irreducible modulo $3$.






          share|cite|improve this answer












          Since $3$ is a primitive root modulo $5$, the fifth roots of unity are in ${bf F}_{81}$, but not in a proper subfield. This means that the cyclotomic polynomial $Phi_5(X)=X^4+X^3+X^2+X+1$ is irreducible modulo $3$.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Jan 1 at 17:40









          Rene SchoofRene Schoof

          26614




          26614























              2














              The elements of $GF(p^n)$ are the zeros of the polynomial $x^{p^n}-x$. This polynomials decomposes into irreducible polynomials of degree $d$ over $GF(p)$ where $d$ divides $n$. It can be shown that this decomposition contains at least one polynomial of degree $n$ which ensures the existence of a finite field with $p^n$ elements. In a CAS you usually have access to such irreducible polynomials.






              share|cite|improve this answer


























                2














                The elements of $GF(p^n)$ are the zeros of the polynomial $x^{p^n}-x$. This polynomials decomposes into irreducible polynomials of degree $d$ over $GF(p)$ where $d$ divides $n$. It can be shown that this decomposition contains at least one polynomial of degree $n$ which ensures the existence of a finite field with $p^n$ elements. In a CAS you usually have access to such irreducible polynomials.






                share|cite|improve this answer
























                  2












                  2








                  2






                  The elements of $GF(p^n)$ are the zeros of the polynomial $x^{p^n}-x$. This polynomials decomposes into irreducible polynomials of degree $d$ over $GF(p)$ where $d$ divides $n$. It can be shown that this decomposition contains at least one polynomial of degree $n$ which ensures the existence of a finite field with $p^n$ elements. In a CAS you usually have access to such irreducible polynomials.






                  share|cite|improve this answer












                  The elements of $GF(p^n)$ are the zeros of the polynomial $x^{p^n}-x$. This polynomials decomposes into irreducible polynomials of degree $d$ over $GF(p)$ where $d$ divides $n$. It can be shown that this decomposition contains at least one polynomial of degree $n$ which ensures the existence of a finite field with $p^n$ elements. In a CAS you usually have access to such irreducible polynomials.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Jan 1 at 17:38









                  WuestenfuxWuestenfux

                  3,7661411




                  3,7661411























                      2














                      I think the state of the art is Couveignes, J. M., & Lercier, R. (2013). Fast construction of irreducible polynomials over finite fields. Israel Journal of Mathematics, 194(1), 77-105. A preprint is available on arxiv.



                      If you want something simpler but better than brute force, you could look at Victor Shoup's work from the 1990s. Shoup, V. (1990). New algorithms for finding irreducible polynomials over finite fields. Mathematics of Computation, 54(189), 435-447 is not the most recent, but is freely available online, unlike the follow-up.



                      Obviously both of these also serve as starting points for a literature search.






                      share|cite|improve this answer





















                      • +1 for the references
                        – Jyrki Lahtonen
                        Jan 2 at 5:40
















                      2














                      I think the state of the art is Couveignes, J. M., & Lercier, R. (2013). Fast construction of irreducible polynomials over finite fields. Israel Journal of Mathematics, 194(1), 77-105. A preprint is available on arxiv.



                      If you want something simpler but better than brute force, you could look at Victor Shoup's work from the 1990s. Shoup, V. (1990). New algorithms for finding irreducible polynomials over finite fields. Mathematics of Computation, 54(189), 435-447 is not the most recent, but is freely available online, unlike the follow-up.



                      Obviously both of these also serve as starting points for a literature search.






                      share|cite|improve this answer





















                      • +1 for the references
                        – Jyrki Lahtonen
                        Jan 2 at 5:40














                      2












                      2








                      2






                      I think the state of the art is Couveignes, J. M., & Lercier, R. (2013). Fast construction of irreducible polynomials over finite fields. Israel Journal of Mathematics, 194(1), 77-105. A preprint is available on arxiv.



                      If you want something simpler but better than brute force, you could look at Victor Shoup's work from the 1990s. Shoup, V. (1990). New algorithms for finding irreducible polynomials over finite fields. Mathematics of Computation, 54(189), 435-447 is not the most recent, but is freely available online, unlike the follow-up.



                      Obviously both of these also serve as starting points for a literature search.






                      share|cite|improve this answer












                      I think the state of the art is Couveignes, J. M., & Lercier, R. (2013). Fast construction of irreducible polynomials over finite fields. Israel Journal of Mathematics, 194(1), 77-105. A preprint is available on arxiv.



                      If you want something simpler but better than brute force, you could look at Victor Shoup's work from the 1990s. Shoup, V. (1990). New algorithms for finding irreducible polynomials over finite fields. Mathematics of Computation, 54(189), 435-447 is not the most recent, but is freely available online, unlike the follow-up.



                      Obviously both of these also serve as starting points for a literature search.







                      share|cite|improve this answer












                      share|cite|improve this answer



                      share|cite|improve this answer










                      answered Jan 1 at 22:32









                      Peter TaylorPeter Taylor

                      8,79312241




                      8,79312241












                      • +1 for the references
                        – Jyrki Lahtonen
                        Jan 2 at 5:40


















                      • +1 for the references
                        – Jyrki Lahtonen
                        Jan 2 at 5:40
















                      +1 for the references
                      – Jyrki Lahtonen
                      Jan 2 at 5:40




                      +1 for the references
                      – Jyrki Lahtonen
                      Jan 2 at 5:40


















                      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.





                      Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                      Please pay close attention to the following guidance:


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


                      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%2f3058677%2firreducible-polynomials-of-degree-greater-than-4-over-finite-fields%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

                      How to send String Array data to Server using php in android

                      Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents

                      Is anime1.com a legal site for watching anime?