Sum collision from two lists of numbers

Question

Suppose you have two large lists of integers of length $N$, and you want to find two pairs $(a_1, b_1)$, $(a_2, b_2)$ from the lists such that $a_1 + b_1 = a_2 + b_2$ (modulo the integer width). Say for example, that $N = 2^{32}+1$ and the integers are 64 bits.

Is there any efficient way to do this? I know that if you are given a particular value, you can easily find the pairs that sum to that value in linear time, so the hard part is finding the colliding sum value in the first place. The obvious approach is $O(N^2)$, but I can't think of anything better.

One other idea I had was to try FFT to do a convolution on the lists, but I don't think that helps because the lists of integers are sparse, while my understanding is that the fourier transform would involve computing $2^{64}$ elements.

This answer says that there is an $O(N^{4/3})$ algorithm if the integers are randomly distributed, but doesn't provide any details.

Answer 1

You can find a solution with an algorithm that requires about $2^{24}$ operations and $2^{22}$ space, and requires only $N=2^{22}$ entries in each list. (If you have more than that in each list, ignore the rest and use only the first $2^{22}$ entries.) Here's how.

Step 1. Build a list $L$ of all of the pairs $(a,b)$ such that $a+b \equiv 0 \bmod 2^{22}$.

By the birthday paradox, we expect there will be about $N^2/2^{22} \approx 2^{22}$ such pairs $(a,b)$, since there are $N^2$ possible pairs and each pair has a $1/2^{22}$ chance of satisfying the condition. To find them, build a sorted list of the values $a \bmod 2^{22}$, a sorted list of the values $-b \bmod 2^{22}$, and merge the sorted lists. Or, use a hash table.

Step 2. Look for two pairs $(a_1,b_1)$ and $(a_2,b_2)$ in $L$ that have the same sum modulo $2^{64}$.

By the birthday paradox, we expect such a solution should exist with high probability, since we have about $2^{22}$ entries in $L$ (and thus about $2^{43}$ candidate solutions) and the condition holds with probability $1/2^{42}$. (Why $1/2^{42}$? Well, their sum is guaranteed to match in the low 22 bits, by the way we constructed $L$. So, we just need their high 42 bits to match too.)