A primitive element of a finite field is a generator of the multiplicative group of the field. In other words, alpha
in F(q)
is called a primitive element if it is a primitive q−1
th root of unity in F(q)
. This means that all the non-zero elements of F(q)
can be written as alpha^i
for some (positive) integer i
.
All elements of the field F_{2^k}
can be written as polynomials of degree at most k-1
with coefficients that are either 1
or 0
. In order to make this complete, your code also needs to output an irreducible polynomial of degree k
which defines the field you are using.
The task is write code that outputs a primitive element of F_{2^k}
of your choosing for each k = 1 .. 32
in order.
Your output must simply list the k
coefficients of the primitive element in any format that you like and then on a separate line the k+1
elements of the irreducible polynomial. Please separate the outputs for each value of k
if possible.
Your code may take as long as you like but you must have run it to completion before submitting your answer.
You may not use any builtin or library function which returns primitive elements of a finite field or tests whether an element is primitive.
An example
For k = 1
the only primitive element is 1
.
For k = 2
we have F_4
. The 4 elements are {0, 1, x, x + 1}
so there are two primitive elements x
and x + 1
. So the code could output
1 1
1 1 1
as the coefficients for example where the second line is the irreducible polynomial which in this case is x^2+x+1
which has coefficients 1 1 1
.