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
up vote 3 down vote accepted

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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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