16
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ Got any examples? \$\endgroup\$ – Okx Jul 1 '17 at 16:49
  • 1
    \$\begingroup\$ May we also output the polynomials and/or field elements encoded as the bits of an integer we output? \$\endgroup\$ – orlp Jul 1 '17 at 17:57
  • \$\begingroup\$ @orlp Yes absolutely. \$\endgroup\$ – user9206 Jul 1 '17 at 17:58
  • 1
    \$\begingroup\$ I think Pari/GP is the only language that has a built-in for this. \$\endgroup\$ – alephalpha Jul 2 '17 at 1:57
  • 1
    \$\begingroup\$ @Lembik OK. Try it online! \$\endgroup\$ – alephalpha Jul 2 '17 at 2:44
1
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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}
\$\endgroup\$
  • \$\begingroup\$ This is nice. I look forward to the Jelly version :) \$\endgroup\$ – user9206 Jul 2 '17 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy