How many iterations for Pollard's $p-1$ with $p = r^k + 1$ for prime $r$? $p$ and $q$ are large primes.
What is the lowest upper bound for the number of iterations for Pollard's $p-1$ algorithm for factoring $N = pq$, provided that $p = r^k + 1$, for a prime $r$, and $r^k + 1 &lt; q &lt; r^{k+1}$?
What is the lowest upper bound for the number of iterations for Pollard's $p-1$ algorithm for factoring $N = pq$, provided that $p = r^k + 1$, for a prime $r$, and $r^k + 1 &lt; q &lt; r^{k+1}$?


Assuming that $p$ is prime, and that $N$ is smaller than 8 billion bits in length, then step 3 of the referenced algorithm will take at most 17 iterations before exiting via condition (a) or condition (b).