For one of the near universal hash functions $f(x) = ax \mod p \mod 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 \mod p \mod m = x \mod 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 \mod p \mod m = x \mod m= r$ that have $f(x)=s$.

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

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

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/

For one of the near universal hash functions $f(x) = ax \mod p \mod m$ where $p$ is prime and $m < p, m>1$, 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)$.

For one of the near universal hash functions $f(x) = ax \mod p \mod 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 \mod p \mod m = x \mod 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 \mod p \mod m = x \mod m= r$ that have $f(x)=s$.