# What are good parameters for an $ax+b \pmod{2^L}$ hash with distinct first n bits of the first $2^n$ inputs?

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?

• @mvw Your improvements to the tex were much appreciated! – mafu Jun 23 '16 at 18:55
• Dear readers, if the question is unclear, I can provide some examples. Please let me know. – mafu Jun 23 '16 at 19:20