Algorithms to find irreducible polynomials of a given degree - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T12:06:10Z http://mathoverflow.net/feeds/question/105543 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/105543/algorithms-to-find-irreducible-polynomials-of-a-given-degree Algorithms to find irreducible polynomials of a given degree pritam 2012-08-26T15:37:11Z 2012-08-26T17:42:30Z <p>I need to know what are the efficient algorithms to find all the irreducible polynomials of a given degree, say \$d\$ over a given finite field, say \$\mathbb{F}_{p^n}.\$</p> <p>One way is to factorize the polynomial \$x^{p^{dn}}-x\$, which is the product of all irreducible polynomials whose degree divides \$d\$, using factorization algorithms and collect all the degree \$d\$ factors. But I guess we are doing some extra job here. Are there better algorithms to find all irreducible polynomials of degree \$d\$ ?</p> <p>I also want to know about the algorithms to find one irreducible polynomial of a given degree over a given finite field.</p> http://mathoverflow.net/questions/105543/algorithms-to-find-irreducible-polynomials-of-a-given-degree/105549#105549 Answer by Felipe Voloch for Algorithms to find irreducible polynomials of a given degree Felipe Voloch 2012-08-26T16:13:21Z 2012-08-26T16:13:21Z <p>If you want to work over <code>\$\mathbb{F}_{p^n}\$</code> then what you wrote is not quite right. What you want is the polynomial \$x^{p^{dn}}-x\$, which is divisible by all irreducible polynomials of degree \$d\$ over <code>\$\mathbb{F}_{p^n}\$</code>.</p> <p>You can first use inclusion-exclusion to extract from \$x^{p^{dn}}-x\$ the factor which is the product of all irreducible polynomials of degree \$n\$ and then factor that. I don't think there is a better way of finding all irreducible polynomials of degree \$n\$.</p> <p>If you only need to find one polynomial, then the best thing is to write down a random polynomial of degree \$n\$ and test for irreducibility. Repeat as necessary.</p> http://mathoverflow.net/questions/105543/algorithms-to-find-irreducible-polynomials-of-a-given-degree/105558#105558 Answer by Igor Rivin for Algorithms to find irreducible polynomials of a given degree Igor Rivin 2012-08-26T17:35:35Z 2012-08-26T17:42:30Z <p>The last word on the second question is this <a href="http://arxiv.org/abs/0905.1642" rel="nofollow">paper of Couveignes and Lercier.</a> The question is highly nontrivial.</p>