Factoring of exponents in Simon's algorithm In derivations of Simon's algorithm (e.g., p. 4), it's often meant to be apparent that
$$(x_0\oplus s)\cdot y=(x_0\cdot y)+(s\cdot y)$$
where $\oplus$ is "direct sum modulo 2", $x_0,s,y$ are all $n$-bit numbers, and the dot products are over their bit representations.
It's not apparent to me though why this works. Why does this work and what is the intuition here? 
 A: The left- and right-hand sides don't have to be equal (for example,
$$
(1\oplus 1)\cdot 1=0\cdot 1=0\ne 2=1\cdot 1 + 1\cdot 1),
$$
but they are congruent modulo $2$.  To see this, you can expand both sides over the bit position $i=1$, $\dots$, $n$ to get
$$
\sum_{1\le i\le n} ((x_0)_i \oplus s_i) y_i=\sum_{1\le i\le n} (x_0)_i y_i + s_i y_i.
$$
Looking at each term in the expansion, both sides vanish if $y_i=0$.  Otherwise, if $y_i=1$, the left-hand side is $(x_0)_i \oplus s_i$ and the right-hand side is $(x_0)_i+s_i$.  These are both even if $(x_0)_i=s_i$ and both odd if $(x_0)_i\ne s_i$.
Another way to see the congruence is to work over the two-element field ${\Bbb F}_2$ and to take the $n$-bit numbers to be in the vector space ${\Bbb F}_2^n$ over ${\Bbb F}_2$.  Doing this makes the dot product a function from ${\Bbb F}_2^n\times {\Bbb F}_2^n$ to ${\Bbb F}_2$.  Also, $\oplus$ becomes vector addition in ${\Bbb F}_2^n$, so the congruence is reduced to the identity
$$
(x_0+s)\cdot y = x_0\cdot y + s\cdot y, \qquad \ \  x_0, s, y\in {\Bbb F}_2^n,
$$
which holds because the dot product is bilinear.
