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].

 

[blue_raver22]

I understand the importance of being able to factorize polynomials by hand, especially in the field of cryptography. It is essential to show that a polynomial is not primitive in order to ensure the security of the encryption algorithm being used.

To factorize large polynomials by hand, there are a few steps that can be followed. The first step is to identify any common factors that the polynomial may have, such as a constant or a variable. Then, the polynomial can be factored using techniques such as grouping, difference of squares, or trial and error.

In the case of x5+x+1, we can see that it is a polynomial of degree 5, meaning it has 5 terms. This makes it a bit more challenging to factorize, but we can start by looking for common factors. In this case, there are no common factors, so we can move on to trying to group the terms. Since the first and last terms have a common factor of x, we can group them together and the remaining terms together.

(x5+x+1) = (x5+1x) + (x)

Next, we can factor out the common factor of x from the first group, and factor out a 1 from the second group.

(x5+x+1) = x(x4+1) + 1(x)

Now, we can see that the first group can be factored using the difference of squares formula, giving us (x2+1)(x2-1). The second group can be factored as x(x-1). Putting it all together, we get:

(x5+x+1) = x(x2+1)(x2-1) + 1(x)(x-1)

At this point, we can see that the polynomial is not irreducible, as it can be factored into two smaller polynomials. However, this does not necessarily mean it is not primitive. To show that it is not primitive, we can use the factorization we found and plug it into the definition of primitive polynomial, which states that a polynomial is primitive if and only if its coefficients are relatively prime and the polynomial is irreducible over the field of integers modulo p, where p is a prime number.

In the case of x5+x+1, we can see that the coefficients are relatively prime, but the polynomial is not irreducible over the field of integers modulo p. This is because when we factor