2
$\begingroup$

I'm working on generating de Bruijn sequences using a non-binary LFSR (as described in [1]). One problem I'm running into is finding all irreducible polynomials which can be then used to parametrise the LFSR to generate different de Bruijn sequences. I found some Python libraries which implement operations on Galois fields but they are mostly incomplete and usually can only verify whether a polynomial is irreducible over a given GF (actually I had a similar problem with finding implementation for q-valued LFSR but I ended up rolling my own). Is brute force, i. e. generating all (monic) polynomials and then checking for irreducibility, the only way?

[1] Philippakis, Anthony A et al. “Design of Compact, Universal DNA Microarrays for Protein Binding Microarray Experiments.” Journal of Computational Biology 15.7 (2008) : 655–665. Web.

$\endgroup$
1
  • $\begingroup$ I guess that's a good point, if only I could find an option to move the thread ;) $\endgroup$
    – Greg Slodkowicz
    Jun 9, 2011 at 17:54

1 Answer 1

7
$\begingroup$

A sieve algorithm should be more efficient than brute force checking. Take all monic polynomials of degree <=k grouped according to their degree, then output all polynomials x+c and cross out their multiples, then output all remaining polynomials of degree 2 and cross out their multiples, etc.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .