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.


migrated from stackoverflow.com Jun 10 '11 at 23:55

This question came from our site for professional and enthusiast programmers.

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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.