A conjecture concerning Pollard rho I'm investigating the Pollard rho factorization algorithm,  searching for a proof that any odd composite can be factorized for some start number. I'm only studying the standard function $f(x)=x^2+1\mod n$, meaning the rest of $x^2+1$ when divided with $n$ and have found this conjecture:

If $n$ is odd then $\;2*|\operatorname {Im} f|=n+1\iff n$ is prime.

I would like to see a proof or a counter-example.
 A: I think your highlighted result is true. Here are some ideas for a proof:
First observe that the image of your function $f$ will be the same size (cardinality) as the image of the squaring function. 
Second observe that since opposites  in $\mathbb{Z}_n$ (i.e., $k$ and $n-k$) square to the same thing, and since only  $0$ is its own opposite (since $n$ is odd); we have that $2|$ Im $f |\le n+1$, with equality only if at most two elements square to the same value; and only $0$ squares to $0$.
For $\Leftarrow)$: Suppose $n$ is an odd prime. it is well known that exactly half the nonzero elements in $\mathbb{Z}_n$ are quadratic residues (perfect squares) $\pmod{n}$.  Also $0$ is a perfect square. The result follows.
For $\Rightarrow)$: Case 1: $n$ is a prime power. Say $n=p^k$ for some odd prime $p$ and some integer $k>1$.  Then multiple elements will square to $0$ (certainly $0$ and $2\cdot p^{k-1}$ both square to $0$). So as noted above, (second observation), the result will hold.
Case 2: $n$ is divisible by (at least) two distinct odd primes. Then $x^2\equiv 1 \pmod{n}$ will have more than two solutions (this is a fairly standard result, that can be proved using the Chinese Remainder Theorem).  So again the second observation above shows that the result will hold.
