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.