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