Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
It seems like some details are missing. What are $g_0$ and $g_1$? What role do they play? Is the small $x$ different from the big $X$? (What does pdta mean here?) – Dylan Moreland Jan 22 '12 at 21:32
What does $w^2(X)$ mean, for that matter? Sorry to be nitpicky but I'd like to know what the question is! – Dylan Moreland Jan 22 '12 at 21:40
thanks by your attention I edit the question, i dont know that mean $w(X)$ the original paper this so, about the question : "How could i prove this?" – juaninf Jan 23 '12 at 0:56
The question looks better now. But what is this "original paper" you mention? Maybe if you tell us where you found it, we could have a look at it and find something there to help solve the problem. – Gerry Myerson Jan 23 '12 at 3:04
see, in the end from right side, page 102 – juaninf Jan 23 '12 at 4:04

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

share|cite|improve this answer
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)$. – Jyrki Lahtonen Aug 27 '12 at 11:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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