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

1 Answer 1

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$
3
  • $\begingroup$ Care to show how did you reach that? $\endgroup$
    – oleiba
    Commented May 12, 2019 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
    Commented May 12, 2019 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
    Commented May 12, 2019 at 23:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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