How to figure out the irreducible polynomial of a polynomial?

AARRRGH

Hello

Does anyone know of an easy way to do this?

Let's say I have the polynomial x6 + x5 + x4 + x3 + x2 + x1 + 1

Does anyone know how I can calculate the irreducible polynomial of this polynomial?

Any help appreciated.

Thank you

LeixlipRed

Under F2 is it?

So, if this polynomial is irreducible under F2 (not sure off the top of my head if it is) then it will not have any factors (under F2). So to check this you need you try all the different combinations. So a linear combined with a quintic. A quadratic and a quartic. And finally two cubics. Is that enough help or are you still totally lost?

Fremen

Well, the one you gave there is irreducible. In general, if all the coefficients are one and the polynomial is of order P - 1 for a prime P, then it's irreducible over the rationals.

--
Sketch of a proof:
You can see this by multiplying your polynomial by (X - 1) then in your case you get (X^7) - 1 thus, you know your polynomial can be written in the form

P = ((X^7) - 1)/(X - 1)

Now make the substitution X = Y + 1, and you get a polynomial which you can apply eisenstein's criterion to. Then since THAT polynomial is irreducible you know your original polynomial is too.
--


There's a formula which lets you split (x - 1)^N up into irreducible factors, you can probably work something out from that. I would but I'm too tired right now, maybe tomorrow.
Wikipedia link here:
http://en.wikipedia.org/wiki/Root_of_unity#Cyclotomic_polynomials

Edit: heh, better say what field you're working with, or we can't help you. My answer assumed you're factoring them in Q

ManofMunster

i don't have a calculator to hand but i think the answer is x21 +1

Fremen

ManofMunster wrote: »

i don't have a calculator to hand but i think the answer is x21 +1

I think those numbers are powers, not coefficients.

AARRRGH

Thank you everyone for the replies.

To answer your questions:

1. Yes, it is in F2. (Sorry I didn't mention this.)
2. The numbers after the x's are powers, not coefficients.

I have followed your steps and I can (roughly) understand what you mean.

Of interest: is there no java applet or anything like that someone can use to enter a polynomial and see what its (if any) irreducible polynomial is? I think this would be quite handy...

LeixlipRed

I assume in an exam you'd have to show method so not sure how helpful a java applet would be. You start by looking at the two factors/roots in F2, 0 and 1. Sub them in. If they do not satisfy the poly mod 2 then the linear/quintic combination is a no go (it's obvious here they don't work). Then you want to divide the poly by the only irred quadratic in F2 which is x^2 + x + 1. If this does not divide in mod 2 with no remainder then you have to divide it by an irred cubic. Then if you have no remainder mod 2 its reducible. And if you do have a remainder mod 2 its irreducible.

ManofMunster

Fremen wrote: »

I think those numbers are powers, not coefficients.

i was jesting, fremen

don't know is my serious answer

AARRRGH

LeixlipRed wrote: »

I assume in an exam you'd have to show method so not sure how helpful a java applet would be. You start by looking at the two factors/roots in F2, 0 and 1. Sub them in. If they do not satisfy the poly mod 2 then the linear/quintic combination is a no go (it's obvious here they don't work). Then you want to divide the poly by the only irred quadratic in F2 which is x^2 + x + 1. If this does not divide in mod 2 with no remainder then you have to divide it by an irred cubic. Then if you have no remainder mod 2 its reducible. And if you do have a remainder mod 2 its irreducible.

Thank you for that.

Do you know of anywhere I can find an example of your steps above?

Fremen

ManofMunster wrote: »

i was jesting, fremen

don't know is my serious answer

Ah, that's the trouble with communicating through text, it's impossible to tell.
In future, be sure to include as :pac: many :pac: pac-man :pac: symbols :pac: as you :pac: can!

LeixlipRed

dublindude wrote: »

Thank you for that.

Do you know of anywhere I can find an example of your steps above?

I'm sure if you googled hard enough you'd find something. Where you the same chap who a few weeks ago was looking for notes in all this stuff? I still have a great set if notes if you need them. Though as I said before they're on paper so you'd have to physically get them off me