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

  • 5
    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](http://acronyms.thefreedictionary.com/PDTA) mean here?)2012-01-22
  • 0
    What does $w^2(X)$ mean, for that matter? Sorry to be nitpicky but I'd like to know what the question is!2012-01-22
  • 0
    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?"2012-01-23
  • 0
    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.2012-01-23
  • 0
    see http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=00490862, in the end from right side, page 1022012-01-23
  • 0
    @Juan: Most regulars here do not have access rights to IEEE Xplore, so it is a bit rude to refer them to such a page. I happen to have such rights, but unfortunately IEEE Xplore gives me a "page not found" error message. Are you sure that you copied it correctly?2012-07-06
  • 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