Primitive polynomials in extended Galois fields

Hello All

I am trying to generate multi-level sequences in extended Galois
fields, GF(4) to be precise, which satisfy the de Bruijn or window
property.

The approach I followed was to use a Linear Shift Register with a
primitive polynomial in GF(4) as the generator polynomial. But this
requires the primitive polynomials to be generated in the extended
finite field. For this I could hardly find any fast algorithm. So I
resorted to generating irreducible polynomials ( using the inbuilt
function from the NTL library at http://shoup.net/ntl/) and checking
them for primitivity - by ensuring that they are of maximal order.

But this seems to be a costly exercise, since finding out the order
requires 4^degree-1 division checks. ( where degree is the degree of
primitive polynomial to be generated). This requires quite a lot of
time when the degree is more than , say 7. So can somebody suggest a
faster method or at least some pointers to any algorithm for this.

Thank you in advance
Anup

.

Relevant Pages

  • Re: Primitive polynomials in extended Galois fields
    ... I am trying to generate multi-level sequences in extended Galois ... fields, GFto be precise, which satisfy the de Bruijn or window ... requires the primitive polynomials to be generated in the extended ... resorted to generating irreducible polynomials (using the inbuilt ...
    (sci.crypt)
  • Multilevel sequences in extended Galois fields
    ... I am trying to generate multi-level sequences in extended Galois ... requires the primitive polynomials to be generated in the extendef ... For this I could hardly find any fast algortihm. ... them for primitivity - by ensuring that they are of maxiaml order. ...
    (sci.math.research)
  • Re: Multilevel sequences in extended Galois fields
    ... I am trying to generate multi-level sequences in extended Galois ... resorted to generating irreducible polynomials (using the inbuilt ... them for primitivity - by ensuring that they are of maxiaml order. ... which will produce you some primitive polynomials of degree 10; ...
    (sci.math.research)