What is end loop condition in Pollard rho algorithm? I am learning Pollard rho algorithm, and I cannot understand end loop condition. As I understand, this algorithm can be applied for number $N$, if we know, that such number has at least one prime factor $p : 1 < p < N$? If it is so, what is the benefit of such algorithm? It turns out that we always should check, whether number has at least one not trivial prime factor. P.S. As I understand, end loop condition of algorithm is flag, indicating whether we have found prime factor. In other words, without "composite number" check, inifite loops are possible?

You never apply Pollard $\rho$ to a number unless you have already proved that the number is composite. But there are ways to prove a number is composite that are far, far faster than looking for a prime factor of the number. Look up "Fermat's Little Theorem".