Two missing numbers

We need to find two integers $a, b$ from a stream of 64-bit integers, using only 2 integer as memory. It is obvious to save $a + b$, the result of XOR of $a$ and $b$. If we somehow define multiplication and compute $ab$, we may be able to solve a quadratic equation and find $a$ and $b$.

Primitive polynomials

Each 64 bit integer can be viewed as polynomial with degree less than 64 modulo 2. The number $1101_2$ is $x^3 + x^2 + 1$. Summing polynomials is the same as XOR of numbers. Polynomials can be multiplied, but the degree of the result is not less than 64. We need to use a “prime” polynomial and compute multiplication modulo that primitive polynomial.

Integer $(a_1a_2\ldots a_k)_2$ corresponds to a primitive polynomial with the identity $$x^k = a_1x^{k-1} + \cdots + a_k.$$ That means if the bit $2^k$ is set in a integer, we can unset that and XOR that integer with $\alpha=(a_1\ldots a_k)_2$.

Primitive polynomials modulo 2 of degree less than 160 have been tabulated by W. Stahnke.

Multiplication

Multiplying polynomials of degree 63 gives a polynomial of degree 126. We can pre-compute terms $x^{64}, \ldots, x^{127}$ modulo $\alpha$ and use them to compute multiplication modulo $\alpha$.

pows = [alpha]
for i in range(1, 64):
    x = pows[-1] << 1
    if (x >> 64) & 1:
        x ^= (1 << 64) ^ alpha
    pows.append(x)
# pows[i] = x^{64+i} modulo alpha

Now we can multiply in $O(k)$.

def Mult(a, b):
    r = 0
    for i in range(64):
        if (a >> i) & 1:
            r ^= (b << i)
    for i in range(64):
        if (r >> (64 + i)) & 1:
            r ^= pows[i]
    r &= (1 << 64) - 1
    return r

Power, inverse, square root

Given $\alpha$, you can reconstruct all the polynomials in the field as $$\{ 0, 1, \alpha, \alpha^2, \ldots, \alpha^{m-2} \}$$ where $m = 2^k$ is the order of field, and $\alpha^{m-1} = 1$. So for every element of the field $c$, we have $c^{m-1}$ equals 1, $c^{m-2}$ is the inverse of $c$, and $c^{m/2}$ is the square root of $c$.

Computing $c^t$ can be done using $O(\log t)$ multiplications.

Quadratic equation

Given $a+b$ and $ab$, we need to calculate $a$ and $b$. That is we need to solve the equation $$x^2+(a+b)x+ab=0.$$

If $a+b=0$, we know $a=b$ so $x=\sqrt{ab}=(ab)^{m/2}$. Otherwise assume $y=x/(a+b)$. The equations is now $$y^2+y=ab/(a+b)^2.$$ The function $f(y)=y^2+y$ is a linear equation in this field. Mainly because $(x+y)^2=x^2+y^2+xy+xy=x^2+y^2$. So if we compute $f(y)$ for every power of 2 greater than 1, we can construct a system of linear equations $Ay=c$ and solve it for $c=ab/(a+b)^2$. The roots of the equations will be $y$ and $y + 1$.

References