# Is exponentiation of a fixed generator modulo a prime collision-resistant?

Let $p$ be a prime number, and $g$ a generator of $\mathbb Z/p\mathbb Z$. For a message $m$, define the hash function $$h(m) = g^m \pmod p.$$ Is $h$ collision-resistant?

• Instructions for beginners: please @mariyana, click "accept" in the accepted answer. – Peter Krauss Apr 21 '18 at 12:50

Let $m$ be arbitrary. Then $m'=m+p-1$ yields a collision with $h(m)=h(m')$ as $m\equiv m'\pmod{p-1}$ and thus by $p-1$ being the relevant group's order $g^m\equiv g^{m'}\pmod p$.
Or formulated differently (using $g^{p-1}\bmod p=1$): $$h(m')=g^{m+p-1}=g^m\underbrace{g^{p-1}}_{1}\equiv g^m=h(m)\pmod p$$
• Strictly speaking, the domain wasn't specified. If the domain was $\{0, 1, 2, \dots, p - 2\}$, then $h$ is injective and so has no collisions at all! – Squeamish Ossifrage Apr 22 '18 at 4:10
• @SqueamishOssifrage But then $h$ also wouldn't be a "hash function" because it would be non-compressing. – SEJPM Apr 22 '18 at 8:07