11
$\begingroup$

Every finite field of characteristic $2$ ist given by $\mathbb{F}_2[x]/P(x)$ for some irreducible polynomial $P\in \mathbb{F}_2[x]$.

For small degree, a simple algorithm gives a way to find $P$. Is there a way to give explicitely the polynomial $P$ for large degrees? I would be interested in a formula like $$x^n+a_{n-1} x^{n-1}+\cdots +a_1 x+a_0$$ where $a_0,\ldots,a_{n-1}\in \mathbb{F}_2[n]$. This might be too much to ask for all degrees, so an infinite sequence of irreducible polynomials would be good.

EDIT: Some sequences have already be given. If you have more to share (with the proof of the irreducibility, either by giving the reference or explaining it), please go ahead.

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ I doubt that there is anything explicit working for all degrees, but an example of infinite sequence of irreducible polynomials is $x^{2\cdot 3^k}+x^{3^k}+1$ $\endgroup$
    – Antoine Labelle
    Nov 11, 2020 at 22:14
  • $\begingroup$ @AntoineLabelle It is a nice sequence. Could you make it as an answer and give either a reference or a proof on the fact that it is irreducible? $\endgroup$
    – Jérémy Blanc
    Nov 12, 2020 at 7:00
  • $\begingroup$ @YCor You added the tag "computer-algebra", that I removed because my question is more related to infinite sequences, and not finite sequences, which can be found with the computer. $\endgroup$
    – Jérémy Blanc
    Nov 12, 2020 at 7:05
  • $\begingroup$ @JérémyBlanc OK I see, sounds more like fitting sequence-and-series then. (You also might want to fix $X$ vs $x$ in the displayed formula.) $\endgroup$
    – YCor
    Nov 12, 2020 at 7:24
  • $\begingroup$ @YCor Thanks I changed it. $\endgroup$
    – Jérémy Blanc
    Nov 12, 2020 at 7:43

4 Answers 4

Reset to default
5
$\begingroup$

For $n=3^k$, the polynomial $p=x^{2n}+x^n+1$ is irreducible over $\mathbb{F}_2$.

Proof: By Rabin's irreducibilty test, it suffices to check that $p|x^{2^{2n}}-x$ and $\gcd(p,x^{2^{2n/3}}-x)=1$.

Note that the order of $x$ mod $p$ is $3n=3^{k+1}$. Hence, since $3^{k+1}|4^{n}-1$ by lifting-the-exponent lemma, we have $p|x^{2^{2n}-1}-1$.

Again by lifting-the-exponent lemma, we have $4^{3^{k-1}}-1=3^km$ for $m$ not divisible by $3$. Hence $x^{4^{3^{k-1}}-1}=x^{nm}\equiv x^n\ \text{or}\ x^{2n} \pmod{p}$ since $x^n$ has order $3$. As $(x^n-1)x^n=(x^{2n}-1)x^{2n}=1$, this mean that $x^{2^{2n/3}-1}-1$ is invertible in $\mathbb{F}_2[x]/(p)$. As $x$ is also invertible, we have shown that $\gcd(p,x^{2^{2n/3}}-x)=1$, as wanted.

Improve this answer
$\endgroup$
2
  • $\begingroup$ nice, thanks for the proof. $\endgroup$
    – Jérémy Blanc
    Nov 13, 2020 at 22:12
  • $\begingroup$ Basically you need that $2$ is a primitive root modulo $3^{k+1}$. Many ways to see that. $\endgroup$
    – Jyrki Lahtonen
    Dec 13, 2020 at 18:46
7
$\begingroup$

The following paper provides an explicit computational approach to your problem:

J. D. Swift: Construction of Galois fields of characteristic two and irreducible polynomials, Math. Comput. 14, 99-103 (1960). ZBL0105.01202.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the reference. I had seen some of these already, and I guess that with the current computers one can go quite far and find all irreducible polynomials of degree $\le d$ for some large $d$. $\endgroup$
    – Jérémy Blanc
    Nov 12, 2020 at 7:01
5
$\begingroup$

Nice question!

The case of self-reciprocal irreducible trinomials and pentanomials is of interest in cryptography.

The linked paper which I was not aware of before your question has the following result, see here

$$x^{3^s10}+x^{3^s9} +x^{3^s5}+x^{3^s}+1$$is a self-reciprocal irreducible pentanomial of degree $3^s10≡ 6 \pmod{12}$ for every positive integer $s$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the answer. It is a nice sequence. $\endgroup$
    – Jérémy Blanc
    Nov 12, 2020 at 7:02
0
$\begingroup$

It seems that for all $k\geq 1$, $X^{2^k}+X+1\in\mathbb{F}_2[X]$ is irreducible (even if I cannot put my finger on the right argument for the moment).

Improve this answer
$\endgroup$
6
  • $\begingroup$ This looks like a nice formula. It would be good to have some proof of this. $\endgroup$
    – Jérémy Blanc
    Nov 12, 2020 at 16:27
  • $\begingroup$ @GreginGre Take a look at my proof for $x^{2\cdot 3^k}+x^{3^k}+1$, I think a similar method could work for this case. $\endgroup$
    – Antoine Labelle
    Nov 12, 2020 at 17:40
  • 2
    $\begingroup$ You polynomial is reducible. Indeed, for any root $a$ of this polynomial in an algebraic closure of $\mathbb{F}_2$, you have $a^{2^{2r}} = (a^{2^r})^{2^r} = (a+1)^{2^r} = a$, so $a$ is in $\mathbb{F}_{2^{2r}}$. If the polynomial were irreducible, it would generate the field $\mathbb{F}_{2^{2^r}}$, which is bigger. $\endgroup$
    – Jérôme Poineau
    Nov 12, 2020 at 18:27
  • $\begingroup$ Strange. My favorite CAS says it is irreducible for $k=1,....,11$. $\endgroup$
    – GreginGre
    Nov 13, 2020 at 9:17
  • $\begingroup$ @GreginGre For $k = 3$, there is even a factorisation over $\mathbb{Z}$: $X^8+X+1 = (X^2+X+1)(X^6-X^5+X^3-X^2+1)$. $\endgroup$
    – Jérôme Poineau
    Nov 16, 2020 at 6:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.