Probability a near universal hash function $ax \bmod p \bmod m$ produces an output from inputs equal modulo $m$

Question

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/

Answer 1

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$.