1

How is a polynomial like $x^5-1$ be factorised in a prime field like $\mathbb{F}_{11}$ for example ? Any advice ?

I was successful in trying all members of $\mathbb{F}_{11}$ to find the roots as described in the answers. Thanks. But I wasn't successful to do the same in $\mathbb{F}_{19}$. and I can't understand why.

MathPowerUser
  • 87
  • 4
    In general factoring is a bit taxing. In your case we know by Little Fermat that $x^{10}-1$ is the product of linear terms $(x-a)$ with $a\in\Bbb{F}{11},a\neq0$. So as $x^5-1\mid x^{10}-1$ it will factor completely into a product of linear factors. A moment's reflection (use Lagrange's theorem) shows that $x-a\mid x^5-1$, iff $a$ is a non-zero square in $\Bbb{F}{11}$. – Jyrki Lahtonen Feb 07 '15 at 21:02

2 Answers2

1

Over any field:

$$x^5-1=(x-1)(x^4+x^3+x^2+x+1)$$

But over the field $\;\Bbb F_{11}\;$ :

$$3^2=9=-2\pmod{11}\implies 3^5=\left(3^2\right)^2\cdot3=(-2)^2\cdot3=4\cdot3=1\pmod{11}\implies$$

$$3^5=1\pmod{11}$$

and also $\;5^2=9=(-2)\implies 5^5=1\;$

and you already have three different roots, so you can factor out a quadratic:

$$x^5-1=(x-1)(x-3)(x-5)(x^2+9x+3)\pmod{11}$$

Now check the above quadratic's discriminant is $\;3\;$ , which is a square, and you can continue factoring.

Timbuc
  • 34,191
  • There's Jyrki's comment, so $x^2+9x+3$ should be reducible. Fortunately, continuing calculations give $4^2+9\cdot4+3 \equiv 5+3+3\equiv 0\mod 11$, so $(x-4)$ is a factor. – HSN Feb 07 '15 at 21:23
  • 1
    Of course: I have a mistake in the discriminant's value. Thanks, editing. – Timbuc Feb 07 '15 at 21:26
  • Thanks for the explanations. For $\mathbb{F}{11}$ it's clear what to do. But how to proceed with $\mathbb{F}{19}$ ? Do you have any advice ? – MathPowerUser Feb 25 '15 at 21:42
  • Exactly the same:check the discriminat modulo $;19;$ – Timbuc Feb 25 '15 at 21:54
  • But i can only find one root. The remaining polynomial is irreducible. How can I split it. Thank you. – MathPowerUser Feb 25 '15 at 22:03
1

There are specialists in this kind of thing, and I am not one of them. But let me say a few things that may help.

First, if the degree of the polynomial is not too big, or if the prime is not too big, the problems are surmountable. I don’t know how I would attack a degree-$1000$ polynomial over $\Bbb F_{1009}$, however, though I might try these tricks:

You certainly want to look for roots. If you’re not in a mood to try all the elements of $\Bbb F_p$, you can try finding the gcd of your polynomial with the polynomial $x^p-x$, because this is the product of all polynomials of form $x-a$ with $a\in\Bbb F_p$. If the gcd is not $1$, it will be the product of all the monic linears, so you really have the roots in hand.

Similarly, if there are no roots, then you might look at $(x^{p^2}-x)/(x^p-x)$. This is the product of all the irreducible monic quadratic polynomials over $\Bbb F_p$. Again, take the gcd of this with your original polynomial, and again, if the gcd is not $1$, then it will be the product of all quadratic factors of your polynomial. You might try this with a random quartic over $\Bbb F_p$ for a prime that’s not too large, and see how it works out.

Lubin
  • 62,818