# Fast algorithm for composing Boolean polynomials

Question: Is there a practically fast algorithm to compose Boolean polynomials ($\mathbb{F}_2[x]$) modulo a fixed Boolean polynomial?

Background: I would like random access within Vigna's xorshift128+ random number generator. Viewing xorshift128+ as a function $f : \mathbb{F}_2^{128} \to \mathbb{F}_2^{128}$, a fixed jump ahead $f^{\circ n}$ can be efficiently computed by precomputing a degree $\le 128$ polynomial $p_n(x) \in \mathbb{F}_2[x]$ modulo a fixed irreducible characteristic polynomial $q(x) \in \mathbb{F}_2[x]$ also of degree 128.

These polynomials compose: $p_n(p_m(x)) = p_{nm}(x) \mod q(x)$. Thus, an arbitrary jump ahead polynomial can be formed from a set of fixed jump ahead polynomials by repeated composition mod $q(x)$.

Unfortunately, efficient composition of polynomials appears quite involved (see e.g., http://users.cms.caltech.edu/~umans/papers/U07.pdf which performs multipoint evaluation over extension fields for the small characteristic case). Involved, unfortunately, means lots of cycles. I am hoping there is something better in the characteristic 2 case.

Note: I wasn't sure where to put this question. It might be a better fit for crypto, but it isn't specifically about crypto since xorshift128+ isn't crypto strength.

EDIT: Whoops, actually I can do what I want with only polynomial multiplication, which is much easier. I'd still be interested in composition, but I'm also fine if the question is deleted.

• I'm guessing that there's not a much faster algorithm for $\mathbb{F}_2$ than for the general case. However, there may be a way to take advantage of the fact that the polynomials you are composing satisfy the multiplicative property that $p_n(p_m(x)) = p_{nm}(x)$ for all $n,m$. In particular, any such family is completely determined by $\{p_n | n \text{ is prime}\}$ and it is necessary and sufficient for $p_n(p_m(x)) = p_m(p_n(x))$ for all prime $n,m$. Not sure how to take advantage of this yet... – Joshua Grochow Apr 11 '17 at 1:23
• I need $p_n$ up to $n = 2^{128}$, so enumerating primes won't help. – Geoffrey Irving Apr 11 '17 at 3:02
• Given $p_{n-1}(x)$, can you derive $p_n(x)$? I'm not quite clear on how $f^{\circ n}$ relates to $p_n(x)$, so I can't tell whether that's possible (e.g., given $p_{n-1}(x)$, obtain the corresponding function $f^{\circ n-1}$, then compose with $f$, then convert to a polynomial -- is that possible?). Not all functions $\mathbb{F}_2^{128} \to \mathbb{F}_2^{128}$ correspond to a polynomial; there are $(2^{128})^{2^{128}}$ many functions with that signature, but only $(2^{128})^{128}$ polynomials. – D.W. Apr 11 '17 at 23:38
• D.W.: The arxiv.org/abs/1404.0390 paper has the details. The polynomial corresponding to $f^{\circ n}$ is $p_n(x) = x^n \mod q(x)$ where $q(x)$ is the characteristic polynomial of the generator as a Boolean matrix. From that polynomial and the first 128 steps of the generator, one can jump forward to $n$. – Geoffrey Irving Apr 11 '17 at 23:45
• From a practical point of view, you should probably forget about asymptotic performance and instead look at hardware support: if you can use Intel SIMD instructions for multiplication in GF(128) then that will almost certainly beat an asymptotically better algorithm which does its field operations manually. – Peter Taylor Apr 12 '17 at 11:07