2
$\begingroup$

How could i prove this?

Let $F$ be a finite field of characteristic $2$ and $g \in F[X]$ an irreducible polynomial. Splitting this polynomial in even and odd part we get $g(X)=g_0(X)^2+Xg_1(X)^2$. Then there exists a polynomial $w \in F[X]$ such that $w^2(X)\equiv X \bmod g(X)$.

  • 0
    I retract my previous comment. The link works now. May be my cookie whitelist was not up to speed? Sorry about that.2012-08-27

1 Answers 1

2

Let us denote the ideal $\langle g(X)\rangle\subset F[X]$ by $I$. As $g(X)$ was assumed to be irreducible, $I$ is a maximal ideal. Thus the quotient ring $K=F[X]/I$ is another finite field of characteristic two. In such a field squaring, $f(t)=t^2$, is a bijection (aka the Frobenius automorphism). Therefore there exists an element $w\in K$ such that $f(w)=X+I$. The element $w$ is of the form $w=w(X)+I$ for some polynomial $w(X)\in F[X]$. Therefore $ X+I=f(w)=(w(X)+I)^2=w(X)^2+I, $ which is exactly the claimed polynomial congruence $ w(X)^2\equiv X \pmod I. $

  • 0
    For the benefit of the readers who do not have access rights to IEEE Xplore: The existence of the polynomial $w(X)$ is just a useful result that is used to reduce the complexity of another algorithm. That other algorithm takes advantage of splitting the polynomial into even/odd parts as shown. Of course (as other posters observed), those even and odd parts are irrelevant for the purposes of proving the existence of the polynomial $w(X)$.2012-08-27