Re: on generation of primitive polynomials

[John Kerl <kerl@mathpost.la.asu.edu>]

Not so.  The code snippet I sent *does* factor a cyclotomic polynomial over
GF(2^k).  The inner part (in y) is GF(2^k), not GF(2).  The outer part (in x)
is polynomials in GF(2^k).  In your notation you used something like "(01) +
(10) x + (11) x^2".  The y's below represent your tuples (11), e.g. (11)
represents y+1.

Re randomized or determistic algorithms, you can select polys at random, or in
lexical order, and test them for irreducibility, then test the irreducibles for
primitivity.  Your chances of hitting irreducibles and/or primitives at random,
or sequentially, are good.

"P. S. Chakravarthi" <chax@cs.iitm.ernet.in> wrote:

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