# Proof that this is not a secure pseudorandom function?

$$p$$ is a large prime number. Consider the following function $$F:\mathbb Z^*_p \times \mathbb D\rightarrow\mathbb Z^*_p$$ where $$\mathbb D=2,....,p-1$$.

$$F_k(x)=x^k \bmod p$$

Proof that it's not a secure pseudorandom function.

What I‘ve tried:

I give a value to $$x_1$$ and obtain $$y_1$$, then I set $$x_2 =y_1+p$$. At the end $$y_1$$ is equal to $$y_2$$. Could this be right or is it totally wrong?

## 1 Answer

Hint: multiplicative property.

What you have tried does not work because $y_1=y_2$ does not hold in general when $x_2=y_1+p$ (further, adding $p$ is identity in $Z_p$ ).

You want to build a distinguisher for $F_k$. Arguably, $F_k(1)=1$ is enough for that, but you can build a more general distinguisher from $F_k(x_1\cdot x_2\bmod p)=F_k(x_1)\cdot F_k(x_2)\bmod p$.