# 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 < q < r^{k+1}$$?

• $\pi(\sqrt[l]n)$ with $l$ being the lower bound you place on $k$ (and $\pi(x)$ being the prime counting function, ie the number of all primes less than or equal to $x$). – SEJPM May 11 at 14:52
• You may want to provide a reference to a description of the algorithm for which you want to find out the number of iterations, so we can be sure to all talk about the same loop... – SEJPM May 11 at 14:54
• Note that there are only 5 known primes of the form $r^k+1$ with $r$ prime; we know that if there is a sixth, it would be quite huge; more than $2^{8589934592}$ – poncho May 11 at 16:28
• @SEJPM look at robin.pollak.io/wizard_factoring.pdf under the algorithm "Wizards don't exist" step 3. – oleiba May 12 at 7:49
• @poncho that's fine, this is a theoretical question provided that this condition occurs. – oleiba May 12 at 7:49

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 < q < 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).
• @oleiba: we always have $p$ be one of 3, 5, 17, 257 or 65537 - a simple examination of the algorithm shows that, at $r=17$ (if not before), we'll always have $a^{r!} - 1$ being a multiple of $p$, and so $d > 1$ (and so the loop will exit, either at iteration 17 or earlier than that) – poncho May 12 at 18:40
• Thanks. That's a good answer but I'm interested in even a lower upper bound dependant on k, and without assuming the size of $p$ (even though I acknowledge that it needs to be huge to exceed this set of known primes) – oleiba May 12 at 23:56