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

• What is $h'(k)$? An arbitrary $\mathbb Z_m\to\mathbb Z_m$ function? – kennytm Jul 17 '15 at 14:53
• Sorry, forgot that. h' is another hash function – Doc Jul 17 '15 at 14:54
• As long as we don't know $h'$, the $\exists k$ makes no sense. – joriki Jul 17 '15 at 14:57
• 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. – kennytm Jul 17 '15 at 15:00
• $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. – 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.)