Re: on generation of primitive polynomials

["P. S. Chakravarthi" <chax@cs.iitm.ernet.in>]

These functions still expect the base field to be binary.
which is not what I want.
The base field can be of characteristic 2. i.e. of the form
GF(2^k). But I need to pick up primitive polynomials
in  GF(2^k)[x]..   In fact, it will be great if I can pick up
all primitive polynomials UPTO  a certain degree atleast
taking into consideration, the complexity of the field as
k becomes larger.
Any method or function in pari/gp that can help me?
OR any known efficient algorithms (randomized or
deterministic)?

thank you,
chax.

John Kerl wrote:

> I believe you want:
>
> 	factorff(polcyclo(2^n-1,2,y^4+y+1))
>
> Wrap that with lift(lift()) for legibility.
>
> Here is some sample computation:
>
> 		\\ Inner modulus, defining GF(16)
> 		im=y^4+y+1;
> 		\\ Inner residue
> 		ir=Mod(1,2)*y;
> 		\\ Primitive element for GF(16).  It has order 15.
> 		ia=Mod(ir,im);
> 	
> 		\\ Factor the cyclotomic polynomial.  There are 64 of them.
> 		n=8;
> 		pols=factorff(polcyclo(2^n-1),2,im);
> 		length(pols[,1])
> 	
> 		\\ Select an outer modulus from the 64 choices.
> 		om=pols[1,1];
> 		lift(lift(om))
> 		\\ Outer residue.
> 		or=Mod(1,2)*x;
> 		\\ Outer element.  Its order is 255 as we are about to see.
> 		oa=Mod(or,om);
> 		lift(lift(lift(oa^255)))
> 		lift(lift(lift(oa^85)))
> 		lift(lift(lift(oa^51)))
> 		lift(lift(lift(oa^15)))
> 	
>
> "P. S. Chakravarthi" <chax@cs.iitm.ernet.in> wrote:
>
>  
>
> > hi all.
> >
> > I'm a newbie to Pari/gp. Is there a way to generate
> > all primitive polynomials over fields of the type GF(2^x)
> > For example (01) + (10) x + (11) x^2  being primitive
> > over GF(4)  in GF(4^2)  (i.e GF(16))
> > Please observe that this is  _DIFFERENT_ from using
> > GF(16)  as GF(2^4)  and asking for primitiveness of
> > something like  1  +  1.x  +  0.x^2  +  0.x^3  +   1. x^4
> > I do not seem to find a way. Actually I was suggested
> > in sci.math.research group to use fxt software ..
> > the author of which, in turn referred me to pari/gp
> > Any help would be appreciated.
> >
> > I have pari/gp installed on my linux comp.
> >
> > cheers,
> > chax.
> >
> > --
> > I might not be the brightest bulb in the chandelier, but I'm pretty 
> > good at getting most of the other bulbs to light up.
> >   -Jack Welch
> >
> >
> >    
>
>  

--
I might not be the brightest bulb in the chandelier, but I'm pretty 
good at getting most of the other bulbs to light up.
  -Jack Welch