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

<p><strong>Background</strong>: I would like random access within Vigna's <a href="https://arxiv.org/abs/1404.0390" rel="nofollow noreferrer">xorshift128+ random number generator</a>.  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.</p>

<p>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)$.</p>

<p>Unfortunately, efficient composition of polynomials appears quite involved (see e.g., <a href="http://users.cms.caltech.edu/~umans/papers/U07.pdf" rel="nofollow noreferrer">http://users.cms.caltech.edu/~umans/papers/U07.pdf</a> 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.</p>

<p>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.</p>

<p><strong>EDIT</strong>: 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.</p>

CC BY-SA 3.0
2017-04-11T01:23:44.803Z
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
CC BY-SA 3.0
2017-04-11T03:02:01.277Z
I need $p_n$ up to $n = 2^{128}$, so enumerating primes won't help.
Geoffrey Irving
CC BY-SA 3.0
2017-04-11T23:38:00.900Z
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.
CC BY-SA 3.0
2017-04-11T23:45:38.487Z
D.W.: The https://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
CC BY-SA 3.0
2017-04-12T11:07:28.073Z
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
CC BY-SA 3.0
2017-04-14T00:13:42.097Z
If you want to compute $x^n \bmod q(x)$ for large values of $n$, that's easy.  Use fast exponentiation ([square-and-multiply](https://en.wikipedia.org/wiki/Exponentiation_by_squaring)).  This will handle values of $n$ up to $2^{128}$ with only 128 iterations, and each iteration does at most one multiplication and squaring modulo $q(x)$, so it should be very efficient.
D.W.
<polynomials>
Fast algorithm for composing Boolean polynomials
Geoffrey Irving
# Fast algorithm for composing Boolean polynomials

(Asked by: username_0 on 2017-04-10)

**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](https://arxiv.org/abs/1404.0390). 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.

**Tags:** polynomials
> **Comments:**
> **username_1**: 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...  
> **username_0**: I need $p_n$ up to $n = 2^{128}$, so enumerating primes won't help.  
> **username_2**: 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.  
> **username_0**: D.W.: The https://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$.  
> **username_3**: 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.  
> **username_2**: If you want to compute $x^n \bmod q(x)$ for large values of $n$, that's easy.  Use fast exponentiation ([square-and-multiply](https://en.wikipedia.org/wiki/Exponentiation_by_squaring)).  This will handle values of $n$ up to $2^{128}$ with only 128 iterations, and each iteration does at most one multiplication and squaring modulo $q(x)$, so it should be very efficient.  

---

## 0 answers

