I'm hashing 64 bit integers via $ax+b \pmod{2^{64}}$. Good parameters mean that, given an $1 \leq n \leq 64$, the first $n$ bits of the first $2^n$ inputs are distinct. How should I chose $a$ and $b$ to maximize the number of $n$ this applies to?
Let me rephrase the question. I'm working with the function
$$ h_{a,b}(x) = a x + b \pmod{2^L} $$
where $L \in \mathbb{N}$ (it's 64) and $a,b,x \in [0;2^L-1]$. In addition, $a$ is an odd number, so that the function is bijective.
For $1 \leq n \leq L$, I'm considering the first $n$ bits of the image of the first $2^n$ natural numbers:
$$ H_{a,b} (n) = \left\{r \, \left\vert \, \exists 1 \leq p \leq 2^n: r = \left\lfloor \frac{h_{a,b}(p)}{2^{L-n}} \right\rfloor \right\} \right. $$
The parameters $a, b$ are successful for an $n$ if $|H_{a,b}(n)| = 2^n$, i.e. all first-n-bits of the first $2^n$ natural numbers are unique.
I'm looking for $a,b$ that are successful for as many $n$ as possible. In particular, for all small $n$.
How should I go about calculating $a$ and $b$? I'm currently running a program to find them, but surely there must be a better way?
