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.

• Do you want to prove that for each composite there is a suitable start-value (which is trivial) or the more pratical version that there is some start value that factors every composite (which is , as far as I know , false) ? Commented Jan 18, 2020 at 11:49
• You can choose a start-value that gives a factor immediately (this is of course somewhat "cheating" and not the situation in practice). But many other choices will do the job as well, of course we do not know in practice which choices will give a factor. Commented Jan 18, 2020 at 12:20
• How is the conjecture related to the problem which choices will give a factor ? It would be nice , if you could motivate the conjecture somehow. Commented Jan 18, 2020 at 12:21
• @Peter - Your'e right. Chosing $X_0$ as a factor of n makes it trivial. Thanks! The conjecture isn't really connected with Pollard rho but appeared during my investigation.
– Lehs
Commented Jan 18, 2020 at 13:19
• @Peter - Thanks again, that completed a post on my blog: forthmath.blogspot.com/2020/01/about-pollard-rho.html
– Lehs
Commented Jan 18, 2020 at 15:23

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.