1
$\begingroup$

If a polynomial $f(x)$ is irreducible over a finite field, does that mean the only factors are $\{1, f(x)\}$?

How would I go about proving a polynomial $f(x)$ is irreducible over a finite field? A bit of searching on StackExchange showed me this:

Irreducibility criterion: A polynomial $P\in\mathbf F_q[X]$ with degree $n$ is irreducible if and only if

  1. $P$ divides $X^{q^n}-X$;

  2. $P$ is coprime with all $X^{q^r}-X$, $\;r=\dfrac nd$, where $d$ is a prime divisor of $n$.

How would I apply this to $f(x) = x^8 + x^4 + x^3 + x + 1$ over $GF(2^8)$?

$\endgroup$
  • $\begingroup$ That degree eight polynomial A) is irreducible over $GF(2)$, but B) has a zero in $GF(2^8)$ and therefore is not irreducible over $GF(2^8)$. $\endgroup$ – Jyrki Lahtonen May 3 '18 at 21:40
  • $\begingroup$ It is the Rijndael/AES polynomial. See here for irreducibility over $GF(2)$. $\endgroup$ – Jyrki Lahtonen May 3 '18 at 21:42
  • $\begingroup$ I am a bit confused. If I want to prove irreducibility over GF(2^8), do I use GF(2) or GF(2^8)? $\endgroup$ – John May 3 '18 at 21:45
  • $\begingroup$ If it is not reducible, how do I factor the AES polynomial over GF(2^8)? $\endgroup$ – John May 3 '18 at 21:49
  • 2
    $\begingroup$ I am fairly sure that you were asked to show that $f(x)$ is irreducible in the polynomial ring $GF(2)[x]$. Any mathematician would say this irreducible over GF(2). But, this isn't the first time I've seen somebody asking for help to prove that it is irreducible over GF(256). It isn't, but apparently there is a confused cryptoteacher out there somewhere. $\endgroup$ – Jyrki Lahtonen May 3 '18 at 21:51
1
$\begingroup$

Yes ‘$f(x)$ irreducible’ means the only divisors of $f(x)$ are $1$ and $f(x)$, up to a non-zero constant factor.

To apply the criterion to $f(x)$, which has degree $8$, you have to check:

  • $f(x)\mid x^{256}-x$ and
  • $f(x)$ is coprime with $x^{16}-x$ (via Euclid's algorithm).
$\endgroup$
  • $\begingroup$ Is there a name for this "Irreducibility criterion"? How would I divide something with such a large exponent? $\endgroup$ – John May 3 '18 at 21:19
  • $\begingroup$ @John You only need to find the remainder of $x^{256}-x$ modulo $f(x)$. That you can calculate relatively easily with the good old square-and-multiply algorithm. $\endgroup$ – Jyrki Lahtonen May 3 '18 at 21:56
  • $\begingroup$ Can you explain what you mean by "only need to find the remainder..."? $\endgroup$ – John May 3 '18 at 22:02
  • $\begingroup$ The criterion is sometimes called Rabin's irreducibility criterion. $\endgroup$ – Bernard May 3 '18 at 22:04
  • 1
    $\begingroup$ You asked to perform the extended Euclidean algorithm (gcdex). $1$ is the gcd of the polynomials, the two other long polynomials are the coefficients of a Bézout's relation between your two polynomials. If you only want the gcd, I guess you should use the gcd function, not gcdex. $\endgroup$ – Bernard May 3 '18 at 22:55
1
$\begingroup$

You don't need a CAS for this low degree polynomial $$f(x)=x^8+x^4+x^3+x+1.$$ A pencil & paper solution follows:

First we calculate the remainders $r_k(x)$ of the monomials $x^{2k}, 0\le k\le7$, modulo $f(x)$. These are: $$ \begin{array}{c|c} k& r_k\\ \hline 0&1\\ 1&x^2\\ 2&x^4\\ 3&x^6\\ 4&x^4+x^3+x+1\\ 5&x^6+x^5+x^3+x^2\\ 6&x^7+x^5+x^3+x+1\\ 7&x^7+x^4+x^3+x \end{array} $$ Producing this table is easy. You get $r_{k+1}(x)$ as the remainder of $x^2r_k(x)$ modulo $f(x)$. You only need to do long division, when $x^2r_k(x)$ has degree $\ge8$.

With this table at hand for referrals we can then easily calculate the remainders $p_\ell(x)$ of $x^{2^\ell}$ modulo $f(x)$. This task is tailor-made for exponentiation by squaring. Clearly we get $p_{\ell+1}(x)$ as the remainder of $p_{\ell(x)}^2$ modulo $f(x)$. Remember that, by Freshman's dream in characteristic two, we can square a polynomial from $GF(2)[x]$ term-by-term. When calculating $p_{\ell+1}(x)$ a term $x^n$ in $p_\ell(x)$ produces a term $r_k\equiv x^{2k}$: $$ \begin{aligned} p_0(x)&\equiv&\equiv & x,\\ p_1(x)&\equiv p_0(x)^2\equiv r_1&\equiv &x^2,\\ p_2(x)&\equiv p_1(x)^2\equiv r_2&\equiv &x^4,\\ p_3(x)&\equiv p_2(x)^2\equiv r_4 &\equiv &x^4+x^3+x+1,\\ p_4(x)&\equiv p_3(x)^2\equiv r_4+r_3+r_1+r_0&\equiv&x^6+x^4+x^3+x^2+x,\\ p_5(x)&\equiv p_4(x)^2\equiv r_6+r_4+r_3+r_2+r_1&\equiv&x^7+x^6+x^5+x^2,\\ p_6(x)&\equiv p_5(x)^2\equiv r_7+r_6+r_5+r_2&\equiv&x^6+x^3+x^2+1,\\ p_7(x)&\equiv p_6(x)^2\equiv r_6+r_3+r_2+r_0&\equiv&x^7+x^6+x^5+x^4+x^3+x,\\ p_8(x)&\equiv p_7(x)^2\equiv r_7+r_6+r_5+r_4+r_3+r_1&\equiv&x. \end{aligned} $$ From this second table we see that

  • The remainder of $x^{16}-x$ modulo $f(x)$ is $p_4(x)-x\neq0$ meaning that $f(x)$ is not a factor of $x^{16}-x$.
  • The remainder of $x^{256}-x$ modulo $f(x)$ is $p_8(x)-x=0$ meaning that $f(x)$ is a factor of $x^{256}-x$.

Therefore we are done.

$\endgroup$
0
$\begingroup$

By definition a non-zero non-unit element $r$ in a ring $R$ is irreducible if whenever $d$ divides $r$, $d$ is either a unit, or $d$ is the product of $r$ by a unit. So the set of divisors may be considerably larger and contains all elements of the field.

$\endgroup$

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.