For one of the near universal hash functions $f(x) = ax \bmod p \bmod m$ where $p$ is prime and $m < p, m>1$ and $x$ ranges over $1 \dots p-1$ , what is the probability that given $x_r \in \{ x | x \bmod p \bmod m = x \bmod m = r\}$, $f(x_r) = s$? That is, find $Pr_{x_r}(f(x_r)=s)$. The probability is the fraction of $x$s such that $x \bmod p \bmod m = x \bmod m= r$ that have $f(x)=s$.

I asked this question a few months ago on the Mathematics Stack Exchange and never got a reply. It's simple enough, but it is either research level or prior research on the question is very hard to search for. The section below is just how I've thought about it and shouldn't be taken too seriously as part of the question. Actually, I suspect that there's a simpler way of approaching it.

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 \bmod m)(x_r \bmod m) + \lfloor \frac{ax_r}{p} \rfloor p \bmod 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 \bmod a)$. This produces on the order of $\frac{a}{p \bmod a}$ $mp$ lengths which may contain an additional solution. (The number of $mp$s is about $\frac{a}{p \bmod 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 \bmod am$. So the actual number of extra solution will be at most $\lfloor \frac{p \bmod am}{mp \bmod 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 \bmod a}$ $mp$s that are smaller than the total range of $f(x_r)$ (that is multiples of $mp$ on the order $\frac{(p \bmod a)(ap)}{a(mp)} = \frac{p \bmod a}{m}$ ) (for instance from the continued fraction expansion of $\frac{a}{p \bmod 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 \bmod p \bmod 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. The question is motivated by computing the hashed modular exponent in hashed variants of Shor's discrete logarithm algorithm from the unitary matrices represent multiplications by power-of-two exponents of the bases as outlined here: https://arxiv.org/abs/1905.10074 and https://quantumcomputing.stackexchange.com/questions/12354/shors-discrete-logarithm-algorithm-with-a-qft-with-a-small-prime-base/

  • $\begingroup$ What is the domain for $f(x)$ and how do you define the probability? $\endgroup$ – Max Alekseyev Aug 20 '20 at 18:08
  • $\begingroup$ The domain can be taken to be $p-1$ $x$'s $1 \dots p-1$ and the probability is the $\#(x_r$ s.t. $f(x_r)=s)/\#(x_r)$ or the fraction of $x$ s.t. $x \mod m =r$ that $f$ takes to $s$. $\endgroup$ – botsina Aug 20 '20 at 23:35
  • $\begingroup$ No. That's true for $a=1$, but in general $ax \mod p \mod m \neq ax \mod m$. $\endgroup$ – botsina Aug 21 '20 at 0:01
  • $\begingroup$ Then in $x_r \in \{ x | x \mod p \mod m =r\}$ "mod p" is redundant. Since $x_r$ belong to the domain of $f(x)$, one can simply say that $x_r \in \{ x | x\mod m =r\}$. $\endgroup$ – Max Alekseyev Aug 21 '20 at 0:57
  • $\begingroup$ True, but keeping the $\mod p$ makes it easier to pick up the meaning at a glance. The range of $x$, however, does need clarification since it should not include $0$ or $0 \mod p$. $\endgroup$ – botsina Aug 21 '20 at 1:10

Denote $\mathbb Z_p^*:=\{1,2,\dots,p-1\}$ and $\mathbb Z_m:=\{0,1,2,\dots,m-1\}$.

I assume $p\nmid a$. Then $f(x) = g(h(x))$, where $h:\mathbb Z_p^*\to \mathbb Z_p^*$ is a bijection defined by $h(x):=ax\bmod p$, and $g:\mathbb Z_p^*\to \mathbb Z_m$ is defined by $g(x):=x\bmod m$.

Let $b:=(p-1)\bmod m$ and $q:=\left\lfloor\frac{p-1}m\right\rfloor=\frac{p-1-b}m$. It follows that $p=qm+b+1$. Let $B:=\{1,2,\dots,b\}\subset\mathbb Z_m$ and $I_B:\mathbb Z_m\to\{0,1\}$ be the indicator function for the set $B$.

Now, for given $r,s\in \mathbb Z_m$, we have the sample space $$X_r := \{ x\in Z_p^*\mid x\bmod m=r\} = \{ cm+r\mid \delta_{r0}\leq c\leq q-1+I_B(r)+\delta_{r0}\},$$ where $\delta$ is Kronecker delta. In particular, we have $|X_r| = q + I_B(r)$. This is the denominator of the probability $\mathrm{Pr}(f(x_r)=s)$. Getting the numerator is trickier.

Sampling of $x_r\in X_r$ corresponds to sampling an integer $c\in [ \delta_{r0}, q-1+I_B(r)+\delta_{r0} ]$, and setting $x_r=cm+r$.

We have $$(1)\qquad 1\leq cm+r\leq p-1.$$ Then $h(x_r) = acm + ar - kp$ for some $k$ (depending on $c$) satisfying $$(2)\qquad 0\leq acm + ar - kp\leq p-1.$$ Finally, $g(h(x_r))=s$ is equivalent to $$(3)\qquad ar - kp = s + mt$$ for some integer $t$ (again, depending on $c$).

The (in)equalities (1), (2), (3) define a polyhedron in the 3D space of $(c,k,t)$, and the numerator of $\mathrm{Pr}(f(x_r)=s)$ equals the number of integer points in this polyhedron. I don't think there is a simple expression for this number in terms of the given parameters $p,m,a,r,s$.

  • $\begingroup$ A search shows that Alexander Barvinok found an algorithm in the 1990s to exactly count the number of integer points in convex polytopes of fixed dimensions (if you vary the dimension the problem is NP-hard). The algorithm involves finding a short rational generating function for the number of integer points and (because the solution is at a pole) calculating its limit with a finite Taylor series. Barvinok's algorithm has been implemented a couple of times (LattE, barvinok), even a parametric version. $\endgroup$ – botsina Aug 25 '20 at 5:14
  • $\begingroup$ Unfortunately, the parametric version only parametrizes the right-hand side of the polytope equation $Ax=b$, so there's no program to find a closed form solution. Unless there's a huge blow up of complexity when the left-hand side is parametrized, it should be possible to write the exact count as a small number of polynomials dealing with special cases of the parameters. A practical choice would be to precompute $m^2$ special cases for fixed $p$ and $m$ for each pair $r,s$ and substitute for different $a$s. $\endgroup$ – botsina Aug 25 '20 at 5:14

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.