MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Re: webMathematica trouble
  • Next by Date: Re: Re: OOP experiments in Mathematica- The Stack
  • Previous by thread: Re: Irreducible Polynomial over GF(2)
  • Next by thread: Summing the term...