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\$
13
  • 4
    \$\begingroup\$ Got any examples? \$\endgroup\$
    – Okx
    Commented Jul 1, 2017 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
    Commented Jul 1, 2017 at 17:57
  • \$\begingroup\$ @orlp Yes absolutely. \$\endgroup\$
    – user9206
    Commented Jul 1, 2017 at 17:58
  • 1
    \$\begingroup\$ I think Pari/GP is the only language that has a built-in for this. \$\endgroup\$
    – alephalpha
    Commented Jul 2, 2017 at 1:57
  • 1
    \$\begingroup\$ @Lembik OK. Try it online! \$\endgroup\$
    – alephalpha
    Commented Jul 2, 2017 at 2:44

2 Answers 2

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.