0
$\begingroup$

In my algo class, we discussed how uniform hashing algorithms aren't the best since it is possible to generate many keys that all hash to the same location.

Take this hashing algorithm for example: h(x,y) = (ax+by) mod p

a and b are fixed constants, and a,b,x,y are within [0,p-1]. p is a significantly large prime.

How would one go about generating pairs x,y so that each pair hashes to the same index?

$\endgroup$
2
$\begingroup$

It's actually pretty easy because the algebra of $\mathbb{Z}_p$ is unusually nice: it is a finite field, and lots is known about this structure.

Let $h_0$ be any congruence class mod $p$. We can create many pairs that hash to $h_0$. Take any $x'$, and solve $h(x',y)=h_0$ for $y$. This is usually doable because the algebra is nice: $$ ax'+by=h_0 \Rightarrow by = h_0-ax'. $$ As long as $b\neq 0$, we can invert it mod $p$ (and this is computationally easy) and get $$ y= b^{-1}(h_0-ax'). $$
The pair $(x', b^{-1}(h_0-ax'))$ now hashes to $h_0$. You can do this for $p$ different choices of $x'$, and you can also play the same game in the $y$-variable.

Example: $p=10067$ is a prime. Suppose we hash by $h(x,y)= 213x+400y$. Here $b=400$ and my modular calculator tells me that $b^{-1}=4958$. Let's create a pair that hashes to $h(1,1)=613$. I'll randomly take $x'=7322$ and solve for $y$ as above: $$ y=4958(613-213\cdot 7322) = 4131. $$ Hence $h(7322,4131)$ should equal $613$, and it does.

Edit: all of the above was done in $\mathbb{Z}_p$, so when I say $b\neq 0$ I really mean that $p$ does not divide $b$ as an integer.

$\endgroup$
  • $\begingroup$ I'm confused at your generated pair b^-1(h0-ax prime). Does this return an integer? I would assume all pairs need both x and y to be integers. Do you think you could clarify this logic with an example maybe? $\endgroup$ – Algoboye Oct 20 '17 at 3:57
  • $\begingroup$ @Algoboye: yes, it is an integer. If $p=13$ we note that $7\cdot 2 \equiv 1 \pmod {13}$ so $7=2^{-1} \pmod {13}$. Similarly $3=9^{-1} \pmod {13}$ $\endgroup$ – Ross Millikan Oct 20 '17 at 4:25
  • $\begingroup$ @Algoboye yes, $b^{-1}$ must be interpreted as an element of the field $\mathbb{Z}_p$: it is not a reciprocal. Ross Millikan's example shows the right way. There are fast algorithms for computing these modular inverses, even modulo an enormous prime $p$, all of this standard crypto algebra. $\endgroup$ – Randall Oct 20 '17 at 11:50
  • $\begingroup$ I'll insert a sample calculation.... $\endgroup$ – Randall Oct 20 '17 at 18:21
  • $\begingroup$ Your example helped a lot. Thank you very much to both of you! $\endgroup$ – Algoboye Oct 21 '17 at 19:05

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.