Re: Multilevel sequences in extended Galois fields

In article <eu8u72$25m$1@xxxxxxxxxxxxxxxx>,
analhaq@xxxxxxxxx <analhaq@xxxxxxxxx> wrote:
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 teh generator polynomial. But this
requires the primitive polynomials to be generated in the extendef
finite field. For this I could hardly find any fast algortihm. 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 maxiaml order.

The order has to be a factor of 4^degree - 1, so you don't have to check
all that many powers of x; and you can calculate x^2n by squaring x^n
modulo the irreducible polynomial.

What I'd recommend is using a fully-fledged computer algebra package;
the one I know is Magma, you can evaluate things on-line at
http://magma.maths.usyd.edu.au/calc/.

Try the program

g:=GF(4); t:=g.1; P<x>:=PolynomialRing(g);
deg:=10;
for r in [1..1000] do
tmp:=x^deg+P![Random(BaseRing(P)) : r in [1..deg]];
if (IsPrimitive(tmp)) then print tmp; end if;
end for;

which will produce you some primitive polynomials of degree 10; change
the value of 'deg' to get primitive polynomials of a different degree.

'g.1' and 'g.1^2' are the two elements of the GF(4) which aren't 0 and 1.

Tom

.

Relevant Pages

  • 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: 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)
  • Primitive polynomials in extended Galois fields
    ... I am trying to generate multi-level sequences in extended Galois ... requires the primitive polynomials to be generated in the extended ... For this I could hardly find any fast algorithm. ... them for primitivity - by ensuring that they are of maximal order. ...
    (sci.crypt)