# Order of element of multiplicative group of finite field mod polynomial

If $K$ is a finite field of size $q$ and $f$ is a degree $n$ polynomial in $K[x]$, then we can form the quotient field by modding out this polynomial. Elements of this quotient field are of the form $\phi + (f)$ where $f$ is the ideal generated by $f$. I've been trying to figure out what the order of $x^2 + (f)$ within the multiplicative group of this field, but I am struggling with how to incorporate the coefficients of this arbitrary polynomial.

I would like to understand the case where $f$ is any polynomial, but I'm struggling to even do the simpler case of when $f$ is monic and irreducible.

• Do you mean $f \in K[x]$ ? – WLOG Apr 2 '14 at 14:59
• Yes I did, thank you, I made the edit. – user139801 Apr 2 '14 at 15:01
• Nitpick: The quotient ring $K[x]/\langle f\rangle$ is a field if and only if $f$ is irreducible. Also $x^2+\langle f\rangle$ belongs to the group of units of this ring if and only if $x$ and $f(x)$ are coprime or, equivalently, $f(0)\neq0$. – Jyrki Lahtonen Apr 3 '14 at 5:53
• There is no easy answer to your question. Knowing the factorization of $f$ into irreducibles gives a lot of information about possible order, but it is still a lot of work to find it. For example I refer to readymade tables of polynomials $f$ such that the order of $x+\langle f\rangle$ is maximal. If this were easy, there would be no need for such tables. – Jyrki Lahtonen Apr 3 '14 at 5:59

First of all, being monic is a trivial restriction; because your polynomial $f = a_n x^n + \cdots + a_1 x + a_0$ has coefficients in your field $K$, adjoining a root of $f$ to $K$ is the same as adjoining a root of the monic polynomial $a_0^{-1} f$. In fancier language, $a_0^{-1} f$ and $f$ are associates in the ring $K[x]$ and so generate the same principal ideal.
The quotient $K[x]/(f)$ is a field only in the simpler case where the polynomial is irreducible, so it does make sense to focus on that case. Otherwise the set of nonzero elements doesn't form a group (consider the ring $\mathbb{F}_2[x]/(x^2)$).
Assuming $f$ is irreducible, we know that the order of $x^2 + (f)$ will divide $q^{\deg(f)} - 1$, but what it is varies depending what $f$ is.
For example, both the polynomials $f = x^2 + 1$ and $g = x^2 + x + 2$ are irreducible over $K = \mathbb{F}_3$, so $K[x]/(f) \cong K[x]/(g) \cong \mathbb{F}_9$, but the multiplicative order of $x + (f)$ is 4 in the former and 8 in the latter, so $x^2 + (f)$ will have respective orders 2 and 4 in the former and the latter.
• If it's just the case that you're having trouble doing the arithmetic with a specific $K[x]/(f)$, the traditional way to do it is to note that, if we write $[c] = c + (f)$ for short, then, for example, since $[f] = 0$ in $\mathbb{F}_3[x]/(f)$, with my example $f$ above, we have $[x^2] = [x^2] - [f] = [x^2 - (x^2 + 1)] = [-1] = $ in $\mathbb{F}_3[x]/(f)$. So you can write everything as $[ax + b]$ by repeated substitution. – jdc Apr 2 '14 at 15:27