1

I have to use the polynomial $X^8 + X^4 + X^3 + X^2 +1$, and given $\alpha$ is a primitive element. So far I have that $\alpha^8=\alpha^4 + \alpha^3+\alpha^2+1$, and the only method for finding the elements of the field known to me is to multiply with $\alpha$ and replace $\alpha^8$ with $\alpha^4 + \alpha^3+\alpha^2+1$. For example, the first 9 elements of the field are $0, 1, \alpha, \alpha^2, ...,\alpha^7$. Then I find the others as

$\alpha^8=\alpha^4 + \alpha^3+\alpha^2+1$,

$\alpha^9= \alpha^5 + \alpha^4 + \alpha^3+ \alpha.$

So on...

My problem with following this system is that I make too many mistakes. Is there another way to construct this field, or is there a pattern that the elements of the field follow?

Cacey
  • 11
  • By construction, $1, \alpha, \alpha^2, \ldots, \alpha^7$ comprise a basis of $GF(2^8)$. – Travis Willse Jun 06 '15 at 05:25
  • @Travis: I know. Please explain that helps me in what way to write explicitly every elements of the field as their linear combination? – Cacey Jun 06 '15 at 05:29
  • I'm not sure quite what you mean, beyond saying that every element is thus uniquely expressible as a linear combination $z_0 + z_1 \alpha + z_2 \alpha^2 + \cdots z_7 \alpha^7$. – Travis Willse Jun 06 '15 at 05:34
  • @Travis: I have to write down each of the 256 elements of the set so that doesn't help me much. – Cacey Jun 06 '15 at 05:40
  • I don't think it makes sense to ask for a shortcut if you literally have to write out 256 separate polynomials. – Travis Willse Jun 06 '15 at 05:41
  • Are you literally trying to simply write down the set of elements of the field? Or are you trying to write them down in a specific order, namely, the $255$ distinct powers of $\alpha$ (together with $0$)? – Greg Martin Jun 06 '15 at 06:20
  • @GregMartin: I'm to write down the distinct powers of $\alpha$. This is a class assignment. – Cacey Jun 06 '15 at 07:45
  • 2
    @Cacey Like Greg says, there are 255 such powers, so all of the nonzero elements of the field (in fact this is a general feature of the multiplicative groups of nonzero elements of finite fields). One can describe an algorithm on the coefficients to speed up your work, but are you certain? you're actually supposed to write all of them out? By my reckoning the answer is $>2800$ symbols long. – Travis Willse Jun 06 '15 at 09:07
  • Your teacher is lucky. My students would protest vehemently if they had to do this for a field of size $>32$. In fact, I don't recall ever doing this by hand for fields of more $16$ myself. OTOH, my programs initialize such tables up to $2^{20}$ or so... – Jyrki Lahtonen Jun 07 '15 at 06:58
  • Google gives this useful looking hit. It may be mildly inconvenient for you because it writes the elements of the field as integers (programmers often do that even though it confuses the algebra quite a bit) that you are to interpret as binary vectors. For example it lists $\alpha^8$ as $29$. This is because, as you correctly observed, $\alpha^8=\alpha^4+\alpha^3+\alpha^2+1$ and $$2^4+2^3+2^2+1=29.$$ If you use that table for checks, then it is not clear to me whether you are less likely to make errors in converting decimals to binary – Jyrki Lahtonen Jun 07 '15 at 07:13
  • Warning: You may find tables of $GF(256)$ in connection with Rijndael cryptosystem. Be aware that those use a different primitive polynomial, and won't help you here. Anyway, I would simply write a code snippet (Mathematica, Matlab,...) and be done with it. – Jyrki Lahtonen Jun 07 '15 at 07:17

0 Answers0