0
$\begingroup$

$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}$?

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

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).

$\endgroup$
  • $\begingroup$ Care to show how did you reach that? $\endgroup$ – oleiba May 12 at 18:30
  • $\begingroup$ @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) $\endgroup$ – poncho May 12 at 18:40
  • $\begingroup$ 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) $\endgroup$ – oleiba May 12 at 23:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.