Uniform Distribution of a mod hash function

Question

I wonder if there is any efficient way to determine whether the hash values of $h(x)=3x\ mod\ 2^{64}$ are uniformly distributed for $x$ being uniformly distributed in $[0,2^{512}-1]$?

I try to approach this by definition: for $y\in[0,2^{64}-1]$, $P(h(x)=y)=P(x=\frac y3+k\cdot\frac{2^{64}}3)$ for a set of intergers $k$.

The range of $k$ depends on $y$ by $0\leq k\leq3\cdot2^{448}-\frac{y+3}{2^{64}}$. So when $y$ is very large or zero, the range of $k$ should differ by one.

Then I conclude that this hash function is not uniformly distributed. But I think this approach is very ineffective and maybe there is even something wrong in my proof.

Could anyone tell me how to approach this question more effectively? Thank you very much!

Answer 1

1. If $X$ is valued in $Z/bZ$ then $X$ is uniform if and only if $E(e^{2i\pi X g/b})=0$ for all $g\in Z/bZ$ except for $g\equiv 0 \ mod\ b.$

2. if $a$ and $b$ have no common divisor, then $aX$ is uniform on $Z/bZ$ if $X$ is uniform on $Z/bZ.$ Proof : if not there exists $g\not \equiv 0 \ mod\ b$ such that $E(e^{2i\pi aX g/b})\neq 0$ and $ag\equiv 0 \ mod\ b$ which contradicts the fact that $a$ and $b$ have no common divisor.

Apply this to $a=3$ and $b=2^{64}.$

3. If $X$ is uniform on $Z/bb'Z$, then it is uniform on $Z/bZ.$ Proof: if not there exists an integer $g$ such that $g\not \equiv 0 \ mod\ b$ such that $E(e^{2i\pi X g/b})\neq 0.$ This contradicts the fact that $E(e^{2i\pi X g/bb'})\neq 0$ for all $g\not \equiv 0 \ mod\ bb'$.

Application $b=2^{64},\ bb'=2^{512} .$