I have the following to prove, unfortunately I am not able to do so. Let h, h' be hash functions: $h(k,i) = (h'(k) + c_{1}i + c_{2}i^2)$ mod $m$. Show the following: if m is prime and $c_{2} \neq 0$ mod $m$ then $\exists k$ s.t. $i \mapsto h(k,i)$ does not define a permutation.

I am not making any progress. Could someone give me a hint? Thanks in advance

  • $\begingroup$ What is $h'(k)$? An arbitrary $\mathbb Z_m\to\mathbb Z_m$ function? $\endgroup$ – kennytm Jul 17 '15 at 14:53
  • $\begingroup$ Sorry, forgot that. h' is another hash function $\endgroup$ – Doc Jul 17 '15 at 14:54
  • $\begingroup$ As long as we don't know $h'$, the $\exists k$ makes no sense. $\endgroup$ – joriki Jul 17 '15 at 14:57
  • 2
    $\begingroup$ I don't think the statement is true, e.g. take $m=2,c_2=1,c_1=0$, then $i\mapsto h(k,i)$ is a bijection no matter how the constant $h'(k)$ is chosen. $\endgroup$ – kennytm Jul 17 '15 at 15:00
  • $\begingroup$ $h'$ is some other hash functions. The form of h(k, i) is the normal form for open adressing quadrat probing. the $\exists k$ part is equivalent to the hash function being surjective for some $k$, that means that the probing will find a free slot in the hash table. I translated the task from my native language, sorry if there are misunderstandings. $\endgroup$ – Doc Jul 17 '15 at 15:00

The original statement is false when $m=2$ and $c_1=0$, mainly because $i^n=i$ for all $n>0$ when $i$ is 0 or 1.

However, it is true when we restrict to primes $m > 2$. The $\exists k$ qualifier is useless, as $h'(k)$ is just a constant and will not affect whether $i\mapsto h(k,i)$ is a bijection.

We will proceed by finding examples showing that $h$ is not an injection.

For the case $c_1=0$, consider $h(k,1)$ and $h(k,m-1)$. Note that $(m-1)^2\equiv 1\pmod m$.

For $c_1\ne 0$, consider two numbers $x, y \in \mathbb Z_m$, suppose $h(k,x)=h(k,y)$, i.e.

\begin{align} \require{cancel} c_2 x^2 + c_1 x + \cancel{h'(k)} &= c_2 y^2 + c_1 y + \cancel{h'(k)} \\ \cancel{c_2} x (x + c_2^{-1} c_1) &= \cancel{c_2} y (y + c_2^{-1} c_1) \\ x (x + c_2^{-1} c_1) &= y (y + c_2^{-1} c_1) \pmod m \end{align}

If we pick $x=0$ and $y=m-c_2^{-1}c_1$, then we find another example showing $h$ is not an injection.

(The statement is not true for non-primes $m$ because $c_2^{-1}$ does not necessarily exist.)

You may find more information about these with "Permutation Polynomial".


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.