### 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

- The Art of Computer Programming, section 3.2.2
- Two missing numbers: https://contest.ucup.ac/contest/1388/problem/6549
- Table of primitive polynomials: https://www.ams.org/journals/mcom/1973-27-124/S0025-5718-1973-0327722-7/S0025-5718-1973-0327722-7.pdf
- Quadratic equation of characteristic 2: https://math.stackexchange.com/a/4392472