Re: Irreducible Polynomial over GF(2)
- To: mathgroup at smc.vnet.net
- Subject: [mg38727] Re: [mg38716] Irreducible Polynomial over GF(2)
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Tue, 7 Jan 2003 07:26:26 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
I am not sure xactly what you are asking for. However, it is easy to
replicate with Mathematica your computation of the number of
irreducible polynomials of the form:
x^50 +x^m + x^n + x^k+ 1
In[1]:=
testQ[{m_, n_, k_}] :=
Head[Factor[x^50 + x^m + x^n + x^k + 1, Modulus -> 2]] ===
Plus
In[2]:=
t = Flatten[Table[{m, n, k}, {m, 49}, {n, m - 1},
{k, n - 1}], 2];
In[3]:=
Timing[ans = Select[t, testQ]; ]
Out[3]=
{75.39*Second, Null}
In[4]:=
Length[ans]
Out[4]=
1421
Andrzej Kozlowski
Yokohama, Japan
http://www.mimuw.edu.pl/~akoz/
http://platon.c.u-tokyo.ac.jp/andrzej/
On Monday, January 6, 2003, at 05:44 PM, flip wrote:
> Hi All,
>
> I saw this posted in another NG and was wondering if this can be done
> in
> Mathematica?
>
>>>> I need an irreducible monic polynomial over Z_2 with degree 50 which
>>>> should also contain only one another power of variable x. So I'm
>>>> interested to know, for example, if x^50 + x^3 + 1 or x^50 + x + 1
>>>> or
>>>> something like them is irreducible in that field.
>>>
>>> There is no such polynomial.
>>> See EIS A073571 here:
> http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/
> eisA.cgi?An
> um=A073571
>> Very interesting link.
>> Well...I saw that I can't use trinomials so I have to change my
>> target:
>> I need a polynomial which should contain as few elements as possible.
>> For example, I truly hope that some expression such as: x^50 + x^m +
>> x^n
>> + 1 would be irreducible over GF(2) for some m and n.
>
> Someone posted this reply ...
>
> You are unlikely to find a list anywhere of the 22517997465744
> irreducible
> polynomials of degree 50 over GF(2). :-)
>
> No polynomial of the form x^50 + x^m + x^n + 1 is irreducible over
> GF(2)
> since 1 is a root.
>
> *** Can Mathematica do this? ***
>
> However, using another system I have found many of the form x^50 +
> x^m + x^n + x^k+ 1 which are irreducible. In fact there are 1421 of
> them and
> 826 of these are primitive. Here are the first 10 primitive
> polynomials of
> this type. (I print only m,n,k):
>
> 1, 2, 16
> 1, 2, 42
> 1, 4, 29
> 1, 4, 36
> 1, 5, 30
> 1, 5, 37
> 1, 6, 47
> 1, 7, 20
> 1, 8, 49
> 1, 10, 47
>
> Thank you, Flip
>
> Remove "_alpha" to email me.
>
>
>
>
>