For a given near universal hash function $f(x) = ax \mod p \mod m$ where $p$ is prime and $m < p$, what is the probability that given $x_r \in \{ x | x \mod p \mod m =r\}$, $f(x_r) = s$? That is, find $Pr_{x_r}(f(x_r)=s)$.

This question differs from the usual question about the probability of collisions in near universal hash functions because $a$ is constant and $x$ is variable and only those $x$ with the same double modulus are considered. The answer appears to be a question of counting off-by-one errors. The answer is very diffent, too. For instance, if $a=1$, $Pr_{x_r}(f(x_r)=s) = \delta_{r,s}$ and if $a = m+3$, $Pr_{x_r}(f(x_r)=s) \approx \frac{1}{m+3} or \frac{2}{m+3}$.

I've thought of three sources of fence post errors in counting the number of solutions.

Firstly, without taking $\mod p$ or $\mod m$, $f(x_r)=s$ occurs only in certain ranges of length $p$ which repeat every $mp$. (Specifically, $s = (a \mod m)(x_r \mod m) + \lfloor \frac{ax_r}{p} \rfloor p \mod m$.) At the end (and the beginning) of the range of $f(x)$ before taking the moduli there can be an additional region of length of $p$ filled with extra solutions. This produces deviations from uniformity on the order of $\frac{p}{ma}$ solutions (and differences of probability on the order of $\frac{1}{a}$).

Secondly, at a 'higher order' there can be two regions at the beginning and end of the range of $f(x_r)$ (again before taking the moduli) where a number $(f(x_r)=s)$-regions of length $p$ have an additional solution each. (That is, there is an additional fence post in the length $p$.) With the addition of each $mp$, the first solution rolls back by $m(p \mod a)$. This produces on the order of $\frac{a}{p \mod a}$ $mp$ lengths which may contain an additional solution. (The number of $mp$s is about $\frac{a}{p \mod a}$ and some fraction of them rounded has an extra solution.) For there to be an extra solution the first $ax_r$ at or after the correct multiple of $p$ must be less than $p - \lfloor \frac{p}{am} \rfloor am = p \mod am$. So the actual number of extra solution will be at most $\lfloor \frac{p \mod am}{mp \mod a} \rfloor + 1$ on each end of the range.

Thirdly, however, since the period is usually not an integer, it seems that there can be higher order fence post errors. If you look at a sequence of large multiples of $\frac{a}{p \mod a}$ $mp$s that are smaller than the total range of $f(x_r)$ (that is multiples of $mp$ on the order $\frac{(p \mod a)(ap)}{a(mp)} = \frac{p \mod a}{m}$ ) (for instance from the continued fraction expansion of $\frac{a}{p \mod a}$ or from powers of 10) there should be fence post errors at the edges of $[0,a(p-1)]$ for each approximation in the sequence. The length of the edge regions where off-by-one errors should be longer for each multiple, but the fraction of off-by-one errors should be proportionally smaller. Thus fence post errors should occur at some constant fraction of the ratio of the lengths of adjacent members of the sequence, so, provided the ratio between the accuracies doesn't vary too much, the total deviation from uniformity should be around $\log p$ solutions.

This means that the average over $a$ deviation from uniformity should be of order $\frac{m\log p}{p}$. So that for a randomly chosen $a$, most of the deviation from a uniform distribution will be in this third higher order source of fence post errors. Since $ax \mod p \mod m$ is only a near universal hash function this shouldn't be a problem, but I'm worried that I might be over thinking it and there might be a simpler way of solving the problem.



You must log in to answer this question.

Browse other questions tagged .