Output a primitive element for each field size

Question

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−1th 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.

Answer 1

Pari/GP, 114 bytes

Inspired by isaacg's answer in another question.

for(n=1,32,for(i=1,2^n,if(sumdiv(2^n-1,d,Mod(x,f=Mod(Pol(binary(2*2^n-i)),2))^d==1)==1,print([x,lift(f)]);break)))

Try it online!

---

If built-ins are allowed:

Pari/GP, 61 bytes (non-competing)

for(i=1,32,print([ffprimroot(ffgen(f=ffinit(2,i))),lift(f)]))

Try it online!

Answer 2

Mathematica, 127 bytes

Do[For[i=2*2^n,PolynomialMod[x^Divisors[2^n-1]+1,i~IntegerDigits~2~FromDigits~x,Modulus->2]~Count~0!=1,i--];Print@{2,i},{n,32}]

Explanation:

If we choose a primitive polynomial as the irreducible polynomial, then $x$ is a primitive element. A irreducible polynomial of degree $n$ is primitive if and only if it has order $2^n - 1$, i.e., it is divisible by $x^{2^n - 1} - 1$, but not divisible by any $x^i - 1$, where $i$ runs through all the proper divisors of $2^n - 1$.

Output:

Outputs integers whose bits are the coefficients of the polynomials. For example, $8589934581$ is $111111111111111111111111111110101$ when written in binary, so it represents the polynomial

$$x^{32}+x^{31}+x^{30}+x^{29}+x^{28}+x^{27}+x^{26}+x^{25}+\\x^{24}+x^{23}+x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+\\x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^9+\\x^8+x^7+x^6+x^5+x^4+x^2+1$$

{2,3}

{2,7}

{2,13}

{2,25}

{2,61}

{2,115}

{2,253}

{2,501}

{2,1019}

{2,2041}

{2,4073}

{2,8137}

{2,16381}

{2,32743}

{2,65533}

{2,131053}

{2,262127}

{2,524263}

{2,1048531}

{2,2097145}

{2,4194227}

{2,8388589}

{2,16777213}

{2,33554351}

{2,67108849}

{2,134217697}

{2,268435427}

{2,536870805}

{2,1073741801}

{2,2147483533}

{2,4294967287}

{2,8589934581}