# 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$). Commented May 11, 2019 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... Commented May 11, 2019 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}$ Commented May 11, 2019 at 16:28
• @SEJPM look at robin.pollak.io/wizard_factoring.pdf under the algorithm "Wizards don't exist" step 3. Commented May 12, 2019 at 7:49
• @poncho that's fine, this is a theoretical question provided that this condition occurs. Commented May 12, 2019 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).

• Care to show how did you reach that? Commented May 12, 2019 at 18:30
• @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) Commented May 12, 2019 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) Commented May 12, 2019 at 23:56