Finding all primitive polynomials of a certain degree in $\mathbb{F}_q$

Question

I am writing an algorithm to find all primitive polynomials in $\mathbb{F}_2[X]$ and I found this theorem :

If $P(X)$ is a primitive polynomial in $\mathbb{F}_p[X]$ of degree $n$ with root $a$, then all other primitive polynomial ( there are $\Phi(p^n - 1)/n$ ) are given by : {$P_s(x)=(x−a^s)(x−a^{sp})(x−a^{{sp}^2})…(x−a^{{sp}^{n-1}}) | gcd(s,p^n−1)=1$} (see the following link http://www.seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/theory.html#AppendixD)

But the thing I don't understand is : {$s | gcd(s, (p^n -1))$} = $\Phi(p^n - 1)$ so with this method we will find $\Phi(p^n - 1)$ polynomials and not $\Phi(p^n - 1)/n$, am I wrong ?

Thank you very much to help me to understand this :)

Answer 1

I have to admit i didn't look at the posted link, but i hope the following thought helps answering your question:

Let $Q(X)\in\mathbb{F}_p[X]$ the minimal polynomial of $a$ over $\mathbb{F}_p$ (so $Q(X)$ divides $P_s(X)$). Then $K:=\mathbb{F}_p[X]/Q(X)$ is a finite field extension of $\mathbb{F}_p$ in which $a$ lives (actually the smallest such one), with $p^r$ elements, where $r:=\deg (Q)\leq n$ (as $K$ is a vector space over $\mathbb{F}_p$ of dimension $r$). Thus $a^{p^r}=a$ (as $K$ is (isomorphic to) the splitting field of $X^{p^r}-X$).

Especially $a^{p^n}=a^{p^r\cdot p^{n-r}}=a^{p^{n-r}}$. So, for some fixed $s_0$ with $\mathrm{gcd}(s_0,p^n-1)=1$, the $n$ choices $s_0,s_0p,s_0p^2,\ldots ,s_0p^{n-1}$ (which are of course all prime to $p^n-1$ as well) result in exactly the same polynomial $P_{s_0}(X)$, or, to put it differently: $P_{s_0}(X) = P_{s_0p}(X) = \ldots =P_{s_0p^{n-1}}(X)$ in $\mathbb{F}_p[X]$ (only the ordering of the factors is changed). On the other hand, all other choices for $s$ yield different polynomials, so there are $\phi (p^n-1)/n$ different Polynomials of the form $P_s(X)$ above.

Kind regards!

Answer 2

First of all you are right in the sense that the formula defines $\Phi(p^n-1)$ polynomials, but there are not necessairily all different. Its like you would say that the polynomials $(x-1)(x-2)(x-3)$ and $(x-2)(x-3)(x-1)$ are different, but if you write out the product you will see that they have exactly the same coefficients. Now how to see that that there are $\Phi(p^n-1)/n$ polynomials we have to show that each polynomial is repeated $n$ times. This is done by Galois Theory which studies automorphisms $\Bbb{F}^n \rightarrow \Bbb{F}^n$ that leaves the "scalars" $\Bbb{F}$ invariant. These automorphisms also permute the roots of any (irreducible and separable) polynomial of degree $n$. For a finite field these automorphisms constitute a cyclic group of order $n$, they are called Frobenius automorphisms