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: [mg38734] Re: [mg38716] Irreducible Polynomial over GF(2)
  • From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
  • Date: Tue, 7 Jan 2003 07:26:57 -0500 (EST)
  • Sender: owner-wri-mathgroup at wolfram.com

Is this what you mean:


<<Algebra`FiniteFields`


FieldIrreducible[GF[2^50],x]


1 + x^46 + x^47 + x^48 + x^50

?

With best regards

Andrzej Kozlowski
Yokohama, Japan
http://www.mimuw.edu.pl/~akoz/
http://platon.c.u-tokyo.ac.jp/andrzej/




On Tuesday, January 7, 2003, at 12:27 AM, Flip wrote:

> Hello Andrzej,
>
> I am assuming that the form is not known, only that we want a 50th 
> degree irreducible.
>
> The solution I posted, I saw in a NG and the person was able to 
> determine the form and then generate the solutions you give below.
>
> Is there anyway to have Mathematica determine the form and generate the 
> solutions?
>
> Thank you, Flip
>
> --- Andrzej Kozlowski <akoz at mimuw.edu.pl> wrote:
>> 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.
>>>
>>>
>>>
>>>
>>>
>> Andrzej Kozlowski
>> Yokohama, Japan
>> http://www.mimuw.edu.pl/~akoz/
>> http://platon.c.u-tokyo.ac.jp/andrzej/
>
> _____________________________________________________________
> Visit our web directory and reference library at http://safebunch.com. 
> Get FREE email for life at ---> http://safebunch.com
>
> _____________________________________________________________
> Select your own custom email address for FREE! Get you at yourchoice.com 
> w/No Ads, 6MB, POP & more! 
> http://www.everyone.net/selectmail?campaign=tag
>
>



  • Prev by Date: Re: Re: OOP experiments in Mathematica- The Stack
  • Next by Date: Re: tabular output
  • Previous by thread: Irreducible Polynomial over GF(2)
  • Next by thread: Re: Irreducible Polynomial over GF(2)