Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I guess that's a good point, if only I could find an option to move the thread ;) –  Greg Slodkowicz Jun 9 '11 at 17:54
add comment

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

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

1 Answer

up vote 7 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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