3
$\begingroup$

Related to this question. I wish to compute $x^n \bmod g(x)$ in $\mathbb{F}_2[x]$ for some fixed and known upfront $g$. This problem pops up in computing the 'pure' CRC function of a bit sequence of an one followed by $n$ zeroes. Omitting a lot of unnecessary information, having a fast method to compute the coefficients of the resulting polynomial lets us very quickly compute CRC-32C checksums via instruction-level parallelism.

My best method to solve this is logarithmic in $n$ and uses a trick vaguely resembling repeated squaring, i.e. I compute $x^{2^n} \bmod g(x)$ in $n$ steps. I am somewhat skeptical of the existence of the closed form, as the period of the binary sequences formed by the resulting polynomial for increasing $n$ seems very high.

We know for a fact that $n < 2^{64}$, so any method requiring reasonable (computationally) amounts of tabulation is acceptable.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ You can factor $g$ and use the Chinese remainder theorem to split $\mathbb{F}_2[x]/g(x)$ into factors. For example if $g$ is separable, it will split as product of finite fields $\mathbb{F}_q$. In each of those $x^n$ will be $q-1$-periodic. $\endgroup$
    – Achim Krause
    Commented Sep 8 at 22:01
  • 1
    $\begingroup$ Your current method is the standard one. Typically in CRC32 applications $g$ will be chosen such that the period of $x$ is $2^{32}-1$. $\endgroup$
    – Peter Taylor
    Commented Sep 9 at 7:32
  • 1
    $\begingroup$ This is question more suitable for cs.stackexchange.com $\endgroup$
    – Max Alekseyev
    Commented Sep 9 at 21:07

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .