MHB Irreducible Polynomial g = X^4 + X + 1 over F2

  • Thread starter Thread starter aadams
  • Start date Start date
  • Tags Tags
    Polynomial
aadams
Messages
2
Reaction score
0
I am really struggling on the following Algebra question:

Consider the Irreducible Polynomial g = X^4 + X + 1 over 𝔽2 and let E be the extension of 𝔽2 = {0,1} with root α of g.

(a) How many elements does E have?

(b) Is every non-zero element of E of the form α^n with n ϵ N (natural numbers)?

(c) Find all roots of g in E expressed in the form ν + µα + λα^2 + γα^3.

(d) Find the roots of X^2 + X + 1 in E.

(e) Find a subfield of order 4 in E.

(f) Could E have a subfield of order 8.

(g) Could X^3 + X + 1 have a root in E?

I have tried part (a) and I think there are 16 elements in E, as I think that E = 𝔽[X]/g𝔽[X] = 𝔽[X]/I where I is the ideal of 𝔽[X]. and so E = {f + I | f ϵ 𝔽[X]}

I then proceeded to carry out long division of f by g and ended up with: E = {ν + µα + λα^2 + γα^3 |γ,λ,µ,ν ϵ {0,1}}

by substituting in 0 and 1 for the values above, I end up with 16 elements of E. I am not sure if this is correct as it seems a bit long winded for part (a) as it is only worth 2 marks.

I would appreciate help with any of the question! Thanks!
 
Physics news on Phys.org
Welcome, aadams! (Wave)

Your answer to (a) looks fine. To answer part (b), you can compute the powers $\alpha^n$ for $n = 1,2,\ldots, 15$ using the relation $\alpha^4 = \alpha + 1$. Note that more generally, the multiplicative group of a finite field is cyclic. For part (c), consider $\alpha, \alpha^2, 1 + \alpha$, and $1 + \alpha^2$. In (d), you want to find two elements $y$ such that $y^2 = y + 1$; look at the powers of $\alpha$ that are of the form $\beta + 1$. Try these out first, then we can discuss (e), (f), and (g).
 
Thank you very much for your help!

I'm still a bit confused on part (b) - I can see that α^4=α+1 and how this helps to write elements as α^n.
I'm not sure how I could write elements such as α^2 + 1 and α^2+α+1 as α^n?? Also with other elements α^3+α, α^3+1, α^3+α^2+α, α^3+α+1 and α^3+α^2+α+1.

Thanks again!
 
aadams said:
Thank you very much for your help!

I'm still a bit confused on part (b) - I can see that α^4=α+1 and how this helps to write elements as α^n.
I'm not sure how I could write elements such as α^2 + 1 and α^2+α+1 as α^n?? Also with other elements α^3+α, α^3+1, α^3+α^2+α, α^3+α+1 and α^3+α^2+α+1.

Thanks again!

You can start with $\alpha^4 = \alpha + 1$, multiply by $\alpha$ and reduce (if necessary). Then repeat the procedure. If in case you don't want to list them all out, the following argument can be used. The multiplicative group of $E$ is cyclic of order $15$, so the multiplicative order of $\alpha$ has to divide $15$. Since neither $\alpha^3$ nor $\alpha^5$ is the identity, $\alpha$ must generate the group. Hence, every nonzero element of $E$ is of the form $\alpha^n$ for some natural number $n$.
 
Thread 'Determine whether ##125## is a unit in ##\mathbb{Z_471}##'
This is the question, I understand the concept, in ##\mathbb{Z_n}## an element is a is a unit if and only if gcd( a,n) =1. My understanding of backwards substitution, ... i have using Euclidean algorithm, ##471 = 3⋅121 + 108## ##121 = 1⋅108 + 13## ##108 =8⋅13+4## ##13=3⋅4+1## ##4=4⋅1+0## using back-substitution, ##1=13-3⋅4## ##=(121-1⋅108)-3(108-8⋅13)## ... ##= 121-(471-3⋅121)-3⋅471+9⋅121+24⋅121-24(471-3⋅121## ##=121-471+3⋅121-3⋅471+9⋅121+24⋅121-24⋅471+72⋅121##...
Back
Top