Check if a polynomial is primitive over a galois field using Magma calculator

Question

I want to check if the polynomial $f(x) = 1 + x^{18} + x^{29} + x^{42} + x^{57} + x^{67} + x^{80}$ is primitive over the Galois Field $GF(2^{80})$ using the Magma Calculator (http://magma.maths.usyd.edu.au/calc/). I have the written the following two scripts to help me verify this. Script 1's output is $false$, while Script 2's output is $true$. Can someone explain why that is? I read through the handbook of functions provided with the calculator (https://www.math.uzh.ch/sepp/magma-2.25.2-ds/HandbookVolume13.pdf), but that wasn't able to help me explain the difference between the two scripts.

Script 1 :

K := GF(2^80);
R<x> := PolynomialRing(K);

f :=  1 + x^18 + x^29 + x^42 + x^57 + x^67 + x^80;

IsPrimitive(f);

Script 2 :

K<x> := GF(2^80);

f :=  1 + x^18 + x^29 + x^42 + x^57 + x^67 + x^80;

IsPrimitive(f);
```

Answer 1

The object $\ f\ $ in your first script is a polynomial of degree $80$ in the indeterminate $\ x\ $ over the field $\ GF\left(2^{80}\right)\ $. It's primitive if and only if all its roots are primitive elements of the field $\ GF\left(\left(2^{80}\right)^{80}\right)=$$\,GF\left(2^{6400}\right)\ $, or, equivalently, if and only if $\ 2^{6400}\ $ is the smallest positive integer $\ n\ $ such that $\ f\ $ divides $\ x^{n-1}-1\ $. The Magma script below shows that $\ f\ $ is primitive over $\ GF(2)\ $, so it divides $\ x^{2^{80}-1}-1\ $, all its roots are primitive elements of $\ GF\left(2^{80}\right)\ $ and it splits completely into linear factors over that field. It's therefore not even irreducible over $\ GF\left(2^{80}\right)\ $, let alone primitive.

The object $\ f\ $ in your second script is a completely different animal. Here, $\ x\ $ is not an indeterminate of any polynomial ring at all, but a primitive element in the field $\ GF\left(2^{80}\right)\ $, and so $\ f\ $, being a polynomial function of $\ x\ $, is also just another element of $\ GF\left(2^{80}\right)\ $. By definition, it's primitive if and only if $\ 2^{80}-1\ $ is the smallest positive integer $\ m\ $ such that $\ f^m=1\ $. If it's not primitive then you must have $\ f^\frac{2^{80}-1}{p}=1\ $ for one of the prime factors $\ p\ $ of $\ 2^{80}-1\ $, and it's easy enough to use the Magma calculator to check that this isn't the case.

Here's a Magma script to verify all the assertions made above:

K<y>:=GF(2^80);
IsPrimitive(y);
R<x>:=PolynomialRing(K);
S<z>:=PolynomialRing(GF(2));
Factorization(2^80-1);
f1:=1 + y^18 + y^29 + y^42 + y^57 + y^67 + y^80;
f2:=1 + x^18 + x^29 + x^42 + x^57 + x^67 + x^80;
f3:=1 + z^18 + z^29 + z^42 + z^57 + z^67 + z^80;
IsPrimitive(f3);
f1^((2^80-1) div 3);
f1^((2^80-1) div 5);
f1^((2^80-1) div 11);
f1^((2^80-1) div 17);
f1^((2^80-1) div 31);
f1^((2^80-1) div 41);
f1^((2^80-1) div 257);
f1^((2^80-1) div 61681);
f1^((2^80-1) div 4278255361);
Factorization(f2);