# Finite field, how to satisfy equation?

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?

• 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... – A.P. Apr 20 '15 at 18:31

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