## Algorithms to find irreducible polynomials of a given degree

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

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

I also want to know about the algorithms to find one irreducible polynomial of a given degree over a given finite field.

-

Extremely sorry for the typo, I was confusing with $\mathbb{F}_p$ – pritam Aug 26 at 16:35

## 2 Answers

The last word on the second question is this paper of Couveignes and Lercier. The question is highly nontrivial.

-

@quid: thanks for the edit, was doing this on iPad... – Igor Rivin Aug 26 at 18:16
@Igor Rivin: Thanks for the link, I was more interested in the second question. – pritam Aug 30 at 6:03

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

If you want to work over `$\mathbb{F}_{p^n}$` 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 `$\mathbb{F}_{p^n}$`.

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

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.

-

This polynomial will be the product of the elementary cyclotomic polynomials $\phi_k(x)$ for $k|p^{dn}-1$ but $k\not | p^{en}-1$ for $e<d$. This is true because each $x^{p^{en}}-x$ factors into a product of elementary cyclotomic polynomials so a polynomial computed from them by inclusion-exclusion does as well, and the elementary cyclotomic polynomials involved, since $p$ does not divide the order of their roots, are still relatively prime mod $p$, so we can easily check which ones are included in the product of ell irreducible polynomilas of degree $d$. – Will Sawin Aug 26 at 16:22
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 21, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9454957842826843, "perplexity_flag": "head"}