XOR-Product Modulo Prime

Question

Every natural number seems to map to a polynomial in binary field GF(2). For example, $11 = 1011_2 \mapsto x^3 + x + 1$, and $x^3 + x + 1 \mid_{x=2}$ gives 11. How naturally can I go between natural numbers modulo a prime like $10^9 + 7$ and their polynomials? Does it depend on if $10^9 + 7$ maps to an irreducible polynomial? (I don't know what the proper terminology is for this mapping.)

More specifically, let $\otimes$ be the XOR-product, computed by doing binary multiplication but XORing the intermediate results instead of adding. This corresponds to polynomial multiplication in the binary field. This comes from Project Euler #813

$$ \begin{align*} \phantom{\otimes 1111} 1011_2 \\ \otimes \phantom{1111} 1011_2 \\ \hline \phantom{\otimes 1111} 1011_2 \\ \phantom{\otimes 111} 1011_2 \phantom{9} \\ \oplus \phantom{1} 1011_2 \phantom{999} \\ \hline \phantom{\otimes 11} 1000101_2 \\ \end{align*} $$

Can I compute $a \otimes b \equiv (a \% m) \otimes (b \% m) \pmod m$ like for standard multiplication? ($\%$ is the modulo operator in programming, for example $5 \% 3 = 2$.) I guess this is like asking $(f \times g)(2) \equiv (f(2) \% m) \times (g(2) \% m) \mod m$.

Example that suggests it's not true: $11 \otimes 11 = 69$, but $(11 \% 7) \otimes (11 \% 7) = 4 \otimes 4 = 16$, and $16 \%7 \neq 69\%7$.

Answer 1

My best guess is that the problem asks for you:

• to compute the power $P(x):=(x^3+x+1)^N$ in the ring $\Bbb{Z}_2[x]$ where $N=8^{12}\cdot12^8=2^{52}\cdot3^8$,
• then to think of $P(x)$ as a polynomial with integer coefficients, and calculate the remainder of $P(2)$ modulo the usual Project Euler prime $q=10^9+7$.

The way I would approach this is to:

1. Compute the power $$p(x)=(x^3+x+1)^{3^8}=\sum_{i=0}^{3^9}b_ix^i$$ in the ring $\Bbb{Z}_2[x]$. Use square-and-multiply to do this. Now you have a list of the coefficients $b_0,b_1,\ldots,b_{19683}$.
2. Then use the trick that in the ring $\Bbb{Z}_2[x]$ squaring is additive to conclude that $$P(x)=\sum_{i=0}^{3^9}b_ix^{2^{52}i}.$$
3. Then calculate the remainder of $\sum_{i=0}^{3^9}b_i2^{2^{52}i}$ modulo $q$ by whatever methodology you want. At this stage it is simply about calculating the remainder of a bunch of large numbers modulo $q$. The techniques have been covered e.g. here.

Observe that only step 1 uses XOR-powers. Step 2 is a trick sometimes called the Freshman's dream (in characteristic two). In step 3 no XORring is done, it is all usual integer arithmetic.

Of course, I may have misinterpreted what Project Euler wants you to do here. Anyway, there is still a non-trivial amount of programming to do to find that sequence of 19684 bits, and then use them in the last stage. Obvious shortcuts involving standard tricks of modular arithmetic apply.