1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you mean $f \in K[x]$ ? $\endgroup$ – WLOG Apr 2 '14 at 14:59
  • $\begingroup$ Yes I did, thank you, I made the edit. $\endgroup$ – user139801 Apr 2 '14 at 15:01
  • 1
    $\begingroup$ 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$. $\endgroup$ – Jyrki Lahtonen Apr 3 '14 at 5:53
  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Apr 3 '14 at 5:59
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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] = [2]$ in $\mathbb{F}_3[x]/(f)$. So you can write everything as $[ax + b]$ by repeated substitution. $\endgroup$ – jdc Apr 2 '14 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.