Suppose we have $\mathbb{F}_{2^5}$ defined by polynomial $x^5+x^2+1$, and (this is homework exercise, which I kinda solved) it is required to find suitable elements $b$, so that it satisfies equation $b^2+b=x^3+1$

In this field, only 32 items and it is not a big deal to reiterate them all, here is cloud.sage script which does that.

Suitable are $b=x^7=x^4 + x^2$ with $b^2=x^{14}=x^4 + x^3 + x^2 + 1$
And $b=x^{22}=x^4 + x^2 + 1$ with $b^2=x^{44}=x^4 + x^3 + x^2$
(It is obvious that in both cases $b+b^2$ gives $x^3+1$)

It is dumb computational iteration, however. Is there any neat ways to get to this result without going through all $32$ elements?

  • $\begingroup$ You may wish to have a look at this algorithm for factoring polynomials over a finite field. On the other hand, your equation has degree $2$, so you can stop looking as soon as you find two solutions... $\endgroup$
    – A.P.
    Apr 20, 2015 at 18:31

1 Answer 1


Write $b = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4$, $a_i \in \{0,1\}$. Then compute $$b^2 + b = (a_2 + a_4) x^4 + a_4 x^3 + (a_1 + a_2 + a_4) x^2 + (a_1 + a_3) x + a_4$$ so if this is to be $x^3 + 1$, we must have $$ \eqalign{ a_2 + a_4 &= 0\cr a_4 &= 1\cr a_1 + a_2 + a_4 &= 0\cr a_1 + a_3 &= 0\cr a_4 &= 1\cr}$$ (all mod 2). It's not hard to find the solution: $a_1 = 0$, $a_2 =1$, $a_3 = 0$, $a_4 = 1$, $a_0$ arbitrary. So $b = x^2 + x^4$ or $1 + x^2 + x^4$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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