# How to convert a polynomial in $GF(p^n)$ into the form $a(x)^k$, with $a(x)$ a generator polynomial.

I basically have two questions:

Given $GF(p^n$) and $g(x)$ an irreducible polynomial:

1. My textbook says that a polynomial is called primitive if $x$ is a generator of the field. The question now is, how can you check to see if an irreducible polynomial is a primitive polynomial?

2. Assuming $x$ is a generator. When given a polynomial $a(x)$, how can one find the (minimal) power $j$ of $x$ so that $x^j \bmod g(x) = a(x)$? I know I can brute force this, i.e. by computing $x^j \bmod g(x)$ for $j$ in $\{0,1,\dots,p^n-2\}$, but I need a manner to find it without doing so.

• If I've understood correctly, the second problem is known as the Discrete Logarithm problem, and no efficient algorithm is known. en.wikipedia.org/wiki/Discrete_logarithm Jun 10, 2013 at 9:34
• Certainly that should be $p^n-2$ in the last sentence? Also it seems that $g$ is supposed to be a polynomial over $\Bbb Z/p\Bbb Z$ (and not over $GF(p^n)$) of degree$~n$; it would be good to be explicit about that. Jun 10, 2013 at 9:37
• Thank you for your very quick response. I'm checking the page out right now, and I'll let you know asap if it's what I meant. @Marc: I think (not at all sure) that x^(p^n - 1) is equal to 1, which is the same as x^0. Therefore, the table would only contain entries for x^p with p in {0,1,...,n^p -2}. Please correct me if I'm wrong. Jun 10, 2013 at 9:37
• Given that this question is labeled galois-theory but not cryptography, it might be assumed that $p$ is a not-so-enormous prime number and $n$ somewhat large (so that working in $\Bbb F_p$ is a lot easier than working in $\Bbb F_{p^n}$ directly)? Maybe $n$ is composite (which would provide some intermediate fields)? Knowing such assumptions would be helpful. Jun 10, 2013 at 9:42
• @ Yoni: I'm pretty sure the problem you linked is the one I have. Jun 10, 2013 at 9:44

The trivial method of checking primitivity would go as follows. I am assuming that you know the factorization of $p^n-1$. Then you should check for each prime divisor $\ell$ of $p^n-1$ that $x^{(p^n-1)/\ell}\not\equiv1\pmod{g(x)}$. This will do it because we know that the order of $x$ in the multiplicative group $GF(p^n)^*$ is a factor of $p^n-1$, so if it is not a factor of any of maximal divisors $(p^n-1)/\ell$, then it must be the maximum.

Let us do the example from your comment: $p^n=3^4$, $g(x)=x^4+x^2+x+1$. I assume that you have already checked that $g(x)$ is irreducible, for otherwise $\mathbb{Z}_3[x]/\langle g(x)\rangle$ won't be the field $GF(81)$.

Here finding the factorization is easy, as $80=16\cdot5=2^4\cdot5$. We are to check that neither $x^{80/2}=x^{40}$ nor $x^{80/5}=x^{16}$ is congruent to $1$ modulo $g(x)$.

Let's do repeated squaring. We get a flying start as $$x^4\equiv x^4-g(x)=-x^2-x-1$$ Therefore $$x^8=(x^4)^2\equiv(-x^2-x-1)^2=x^4+2x^3+2x+1\equiv 2x^3+2x^2+x\pmod{g(x)}$$ and continuing $$x^{16}\equiv(-x^3-x^2+x)^2=x^6+2x^5+2x^4+x^3+x^2\equiv x^3+2\pmod{g(x)}.$$ So we know that the order is not a factor of 16. Still need to check $40$.

We calculate $$x^{32}\equiv (x^3-1)^2=x^6+x^3+1\equiv x+2\pmod{g(x)},$$ and finally $$x^{40}=x^{32}\cdot x^8\equiv(x-1)(-x^3-x^2+x)=-x^4-x^2-x\equiv1\pmod{g(x)}.$$

Bummer, this means that the polynomial $g(x)$ is not primitive.

We can check similarly that $x^{20}\equiv-1\pmod{g(x)}$, so the order of $x$ is exactly $40$ (not a factor of either 20 or 8).

In general the problem of your second question is difficult (agree with Yoni and Marc), so you should expect a trick to do the specific case of $g(x)=x^4+x^2+x+1$, $a(x)=x+2$.

In the first part we saw that $g(x)$ is not primitive, so the (coset of $x$) only generates a subgroup $H$ of order 40 containing exactly half of the non-zero elements of $GF(3^4)$. We can seek to solve the discrete logarithmg problem in this subgroup. WARNING: As $x$ is not a primitive element, we may not succeed. It may happen that $a(x)\notin H$, and then no $j$ works.

Indeed, the following trick gets us started. $$x^2+x+1=x^2-2x+1=(x-1)^2=(x+2)^2.$$ So if we have $$a(x)\equiv x^j\pmod{x^4+x^2+x+1},$$ we also have $$x^{2j}=a(x)^2=x^2+x+1\equiv-x^4.$$ Given that $x$ is of order $40$ we get that $$x^{20}\equiv-1,$$ as $x^{20}$ is of order two, and $-1$ is the only element of multiplicative order two. Therefore $$x^{2j}\equiv x^{24}\pmod{g(x)}.$$ As the discrete logarithm is defined modulo $\operatorname{ord}(x)=40$, we get $$2j\equiv 24\pmod{40}\Leftrightarrow j\equiv 12\pmod{20}.$$ This leaves two choices $j=12$ and $j=32$. While checking out primitivity of $g(x)$ we actually saw that $j=32$ works. Didn't want to draw any attention to that earlier.

• This is a very elementary example of so called index calculus. Not complete, mind you. Brute forcing $p^n=81$ would be trivial on a computer. When $p^n=2^{300}$ or something liket that you have a real problem. Jun 10, 2013 at 10:57
• I'm a bit confused; I'm trying to figure out what confuses me. I'd say that if x is a generator, x^i != x^j with i != j and both in {0,1,...,79}. Other than that; I brute forced by hand to x^15 = x + 2. I'm still trying to understand it all; just giving you a heads-up. Jun 10, 2013 at 11:14
• @jvanheesch: There is an error somewhere. When I started checking it turned out the $g(x)$ is not primitive after all. I redo the latter part. Jun 10, 2013 at 11:22
• You seem to be correct that g(x) is not primitive. Which is actually interesting for question A., which is the question whether or not there's a quick way to find out if an irreducible polynomial is primitive. Aside from that, I found the shortcut possibility (i.e. mathematical insight in the given numbers) very interesting; will surely look out for that on my exam. Jun 10, 2013 at 12:08