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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.