How Do I Factorize Large Polynomials by Hand?

[miahmad]

Basically, i am doing some cryptography, i need to show that a polynomial i have, which is not irreducibale, implies it is not primitive.

I am having trouble factorising these rather large polynomials.

I have checked to see whether the following polynomials are irreducible and found there factorisation with maple.
Could someone please teach me how you would do these by hand.
x⁵+x+1=(x²+x+1)(x³-x²+1)

Another example:

x⁵+x⁴+1=(x²+x+1)(x³-x+1)

an explanation of either would be gratefuly appreciated, thank you.

 

[Simon_Tyler]

Since you've already solved these using maple, I assume you know that they can not be factored using real numbers, where best that you can do is what you already had. There is one real root and 2 pairs of complex conjugate roots, which is what you need for the polynomial to have real coefficients.

Since your polynomials factor to a cubic times a quadratic you just need to solve each separately. Thus you need the quadratic formula and the cubic formula.
The quadratic formula is derived via completing the square.
The standard derivation of the cubic is on the http://en.wikipedia.org/wiki/Cubic_function" .

 

[Hurkyl]

Your post doesn't make sense. Could you clarify? The problem you seem to be trying to solve has nothing to do with actually performing any sort of calculation, so I don't understand why you are asking about how to factor polynomials.

For this specific example, the proof of the rational root theorem could be adapted to minimize the number of cases to consider, at which point you could just solve an equation to see if there was a nontrivial factorization.

What ring are you trying to factor over? Even if the integers, you could get a head start by factoring first over one or more finite fields.

I'm not sure why you would want to factor by hand, though...

 

[ohubrismine]

Basically, i am doing some cryptography, i need to show that a polynomial i have, which is not irreducibale, implies it is not primitive.

I am having trouble factorising these rather large polynomials.

I have checked to see whether the following polynomials are irreducible and found there factorisation with maple.
Could someone please teach me how you would do these by hand.
x⁵+x+1=(x²+x+1)(x³-x²+1)

Another example:

x⁵+x⁴+1=(x²+x+1)(x³-x+1)

an explanation of either would be gratefuly appreciated, thank you.

I'm assuming that since your application is cryptography, the UFD of interest to you is the integers.
Note that x^5+x^4+1 is primitive in Z[x], the gcd of the coefficients is 1, even though it is reducible. So there is already a counterexample to your conjecture: if f(x) is not irreducible, then it is not primitive.
As far as factoring large polynomials, there is no simple formula unless the polynomial is quadratic in form. Quintics are not solvable by radicals in general and so very few indeed will be reducible over Z[x].