Given a prime p, we let $x_0 = 1$, and $x_{i+1} = (x_i^2+1) \mod p$. Since there are only p possible values for $x_i$, so eventually these values must repeat. Assuming that $x_i$ behaves like being random, the smallest I is expected to be quite small.
What will happen when we calculate $x_i$? For a while we get all different values. Then a value gets repeated, that is $x_n = x_m$, and from then on the values repeat in a cycle of length m-n.
Now the algorithm calculates two sequences: One step at a time, and two steps at a time. After n steps the “slow” sequence enters the cycle. The “fast” sequence at this point is somewhere in the cycle and would need k steps to reach the start of the cycle. Since the fast sequence does two steps where the slow one does one, after each 1/2 steps the fast sequence comes one closer to the slow one, and after k 1/2 steps both meet. At that point $x_i = x_{2i}$.
Note that we have no idea what n, m and k are, but we still will find the point where both sequences meet.
And this is just Floyd’s cycle finding algorithm. Pollard-rho is much more clever. Given is N, and we want to find factors of N. Let p be a prime factor of N. Then we calculate $x_{n+1} = (x_n^2+1) \mod p$ and $y_{n+1} = (y_n^2+1) \mod N$ in parallel. At some point we find an i such that $x_i = x_{2i}$. At that point $y_i = y_{2i} \mod p$ and $gcd(y_i - y_{2i})$ is a multiple of p.
We don’t actually have any idea what p is, since finding p is what we try to achieve! So we never actually calculate $x_i$. Nevertheless, p is a divisor, so we will find i with $gcd(y_i - y_{2i}) = g > 1$, and that g is a divisor of N.
