Two missing numbers

We need to find two integers $a$ and $b$ from a stream of 64-bit integers, using only two integers 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 a polynomial with degree less than 64 modulo 2. The number $1101_2$ is $x^3 + x^2 + 1$. Summing polynomials is the same as the XOR of numbers. Polynomials can be multiplied, but the degree of the result is not less than 64. We must use a “prime” polynomial and compute multiplication, modulo that primitive polynomial.

$$x^k = a_1x^{k-1} + \cdots + a_k.$$

So if the bit $2^k$ is set in an 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$.

1
2
3
4
5
6
7

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

$$\\{ 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

$$x^2+(a+b)x+ab=0.$$$$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