1
$\begingroup$

Carter and Wegman introduced in the paper Universal Classes of Hash Functions the $H_{1}$ universal class of hash function. This is essentially the function $h_{a,b}(x) = ((a\cdot x+b)\mod p)\mod m$. I am using here the more common notation from CLRS book respective description, and not from the paper.

Some notation:

  • $x$ is the input to hash function (the key) and takes values in $\{0..u-1\}$
  • $p$ is a prime $\geq u-1$
  • $a$ is a random number in $\{1..p-1\}$
  • $b$ is a random number in $\{0..p-1\}$
  • And obviously the outputs of hash function are in $\{0..m-1\}$

The problem is that if key word $x$ is large enough, the multiply and add operation involved in the hash function maybe lead in an overflow. For example if $u= 2^{32}$, $x= 2^{32}-1$, then we cannot hold the outcome of $a\cdot x + b$ in a 32-bit word. But even if we can (using 64 bit word) the least prime $p$ we can use is $4294967311$ which can be represented by 34 bits. In that case $a$ and $b$ will possibly have values of 34 bits long, so a 64 bit word can't hold the outcome of $a\cdot x + b$ leading in an overflow.

The authors of the paper describe a way to manipulate longer integers in proposition 8 and the following paragraph, using hash functions working with shorter integers.

Can anyone please demystify the way we can extend this function to manipulate longer integers and why this is working? The paper can be found here here

$\endgroup$
1
$\begingroup$

I believe Schrage's method is exactly what you are looking for.

But for a general method of computing $ax + b \bmod m$ where $a, b, x, m$ all fit in a single CPU word and all are unsigned values I can quickly explain a method. I assume a CPU word has size $2^w$ and overflow is just modulo $2^w$.

First, computing $x + y \mod m$. Reduce $x, y \mod p$ (not necessary if you already know $x, y < p$). Then, if $y \geq m - x$, overflow would occur. So in that case we compute $x + y - m$, otherwise simply $x+y$. In C++:

// Compute (x + y) % m, assumes x, y < m.
uint64_t addmodu64(uint64_t x, uint64_t y, uint64_t m) {
    return x + y - m * (y >= m - x);
}

Then, computing $xy \bmod m$ can be done by multiplication through repeated addition in $O(\log x)$ additions. We can repeatedly apply the following identity:

$xy \equiv (2\lfloor{x\over2}\rfloor + (x\bmod 2))y \equiv 2y\lfloor{x\over2}\rfloor + y(x\bmod 2) \mod m$

This gives a recursive function:

// Compute (x * y) % m, assumes x, y < m.
uint64_t mulmodu64(uint64_t x, uint64_t y, uint64_t m) {
    if (x == 0) return 0;
    uint64_t y2 = addmodu64(y, y, m);
    uint64_t r = mulmodu64(y2, x/2, m);
    if (x % 2) r = addmodu64(r, y, m);
    return r;
}

This is just for demonstration purposes, for a fast implementation you want to convert this to a loop without any calls.

Finally, computing $(ax + b \bmod p) \mod m$ then is as simple as addmodu64(mulmodu64(a, x, p), b, p) % m.

$\endgroup$
  • $\begingroup$ I think this is not applicable solution. Because Schrage's method would be convenient if hash function was of the type $ax \mod p$ and also would be valid if $a^2 < p$ which is not true either $\endgroup$ – Curious_Dim Apr 30 '17 at 1:07
  • $\begingroup$ @Curious_Dim Once you found $ax \bmod p$ then adding $b\mod p$ is trivial. And $a^2 < p$ is not required, only $p \bmod a < \lfloor p/a \rfloor$. If your $a$ does not satisfy this you can always split $a = m + n$ such that the requirement holds for $m, n$ and then compute $nx + mx + b \bmod p$. $\endgroup$ – orlp Apr 30 '17 at 11:31
  • $\begingroup$ @Curious_Dim I added general methods to my answer. $\endgroup$ – orlp Apr 30 '17 at 12:15

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.