I just discovered that my home computer can go through this entire 32-bit space in a few seconds (without even using multiple threads), so brute force works just fine for my current purposes (reverse engineering an unusual CRC computation). My old maxim on optimization still stands: code the quick-and-dirty method, and use the time waiting for that answer to think about faster methods; if the answer comes back before you've thought of a better method, then you may not need a better method. At 11:26 AM 6/24/2017, Henry Baker wrote:

This question is related to CRC polynomials, so the degree of the polynomials I'm (currently) concerned with are on the order of 32 -- i.e., far too small for crypto applications.

The coefficients are 0's and 1's; denote the coefficient field F2 with elements {0,1}.

Consider the polynomials in "x" over F2, i.e., F2[x].

Suppose we have a fixed polynomial p(x) in F2[x] of degree n, where n is in the approximate range of 32.

We will work in the ring F2[x]/p(x), whose representatives will be the remainders of polynomials f(x) in F2[x] after division by p(x). Clearly, if r(x) is such a remainder, degree(r(x))<degree(p(x))=n.

Now consider the multiplicative group generated by x itself in the ring F2[x]/p(x).

We will **NOT** assume that p(x) is irreducible, so F2[x]/p(x) is not necessarily a finite field, and x may not generate the complete multiplicative group of F2[x]/p(x).

I'd like to compute logarithms base x in this ring -- i.e., given the representative for the ring element x^i, I'd like to efficiently compute i.

Is there any non-table-lookup method or any non-linear-search method for computing this discrete log?

What about when p(x) IS irreducible -- i.e., F2[x]/p(x) really is a finite *field* ?

BTW, since 32 is reasonably small, I'm willing to do a lot of precomputation; I just don't want to have to store a large table, and I'd love the final algorithm to be extremely fast.