My Math Forum Irreducible polynomial

 Abstract Algebra Abstract Algebra Math Forum

 February 13th, 2009, 07:41 AM #1 Newbie   Joined: Feb 2009 Posts: 4 Thanks: 0 Irreducible polynomial Dear friends I've a little problem with this statement: Prove that the trinomial $x^{2n}+x^{n}+1$ is irreducible over GF(2) if and only if $n=3^k$ for some nonnegative integer k. Any help will be highly appreciated.
 February 14th, 2009, 07:52 AM #2 Senior Member   Joined: Dec 2008 Posts: 160 Thanks: 0 Re: Irreducible polynomial Consider this: $x^{2n} + x^n + 1= \frac{x^{3n} - 1}{x^n - 1}$ if n is not power of 3, i.e $n= 3^kp$, then $x^{3^{k+1}p} - 1= (x^p - 1)(x^{p(3^{k+1} - 1)} + ... + 1)$ - reducible over GF(2) If $n= 3^k$, then the only element that can be the root of $x^{3^{k + 1} - 1$ and not of $x^{3^k} - 1$ is primitive element of $GF(2^{3^{k + 1}})$. Lets set q - is such element, then $Q= q^{3^k}$ - has order 3. So the last things to prove is that $Q^2 + Q + 1$ - is irreducible over GF(2), that is known fact.
 February 14th, 2009, 08:29 AM #3 Newbie   Joined: Feb 2009 Posts: 4 Thanks: 0 Re: Irreducible polynomial Thanks for help!
 February 14th, 2009, 09:44 PM #4 Member   Joined: Jan 2009 Posts: 72 Thanks: 0 Re: Irreducible polynomial Zolden, sorry I am rusty, but would you clarify the last step? We know x^2n + x^n + 1 factors over some extension as (x^n-alpha)*(x^n-beta), alpha, beta the roots of the irreducible x^2 + x + 1, but what fact do we need to assert that these terms don't admit grouping into a factorization over GF(2)? Appreciate the pointer... G
 February 16th, 2009, 05:13 PM #5 Senior Member   Joined: Dec 2008 Posts: 160 Thanks: 0 Re: Irreducible polynomial Sorry for cumbersome explanation, did not elaborate for the last step. Consider $GF(2^{3^{k + 1}})$. All roots of $P= x^{3^{k + 1}} - 1$ are there, roots of $Q= x^{3^{k}} - 1$ as well. When we divide first over second, the only will be left roots that are strictly belong to the first one. They are in the form $a, a^2, a^4, a^5, a^7, a^8 ...$, where $a$ is a primitive of our GF. To see that such polynomial does not exist, consider following. Lets see how first coefficient of the result polynomial is formed. It is sum of our roots. Sum of series belongs to GF(2), but if we remove any subset of it - it will not. If $P$ is divisible on any polynomial of GF(2) - we could remove subset (those sum is in GF(2)) of roots and the left sum will still be in GF(2), $Q$ is the only one like this. Divisor degree has to divide $3^{k + 1}$ and be less than it. Any polynomial with lesser degree cannot has roots from higher extension field. So all polynomials have roots only as linear combination of primitive elements from $3^k$ and its powers, so it will not remove any other roots of $P$, other than those, that already removed by $Q$. For the first step: set $y= x^{3^{k}}$, then: nominator is $y^{3p} - 1= (y^p - 1)(y^3 - 1)(y^{whatever} + ... + 1)$, while denominator is $y^p - 1$. So it is reducible. Hope I am clear this time.

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post fleur Abstract Algebra 4 April 15th, 2011 03:08 AM Dlarahasle Algebra 0 February 13th, 2011 10:12 AM lime Number Theory 5 September 23rd, 2010 02:01 AM numbertheory12 Abstract Algebra 0 December 9th, 2008 04:02 PM numbertheory12 Number Theory 0 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top