5
$\begingroup$

Are there some pattern of "bad" numbers for Pollard-Rho algorithm (e.g., numbers for which the algorithm often fails)?

I read a comment here (https://stackoverflow.com/questions/48196783/does-pollard-rho-not-work-for-certain-numbers) saying "it often fails on even numbers and perfect powers". Is this true?

Also, I notice a lot of implementations check even numbers separately. Are there any mathematical reasons? Or is it just a simple heuristic?

$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

It depends on your choice of polynomial.

You can't extract even factor using Pollard-Rho algorithm because of your choice of $f(x)=x^2+1$. For any integer $x$ then $f(f(x))-f(x)$ is always odd. Indeed, we have $f(f(x))-f(x)=(x^2+1)^2-x^2$ where $x^2+1$ and $x$ have different parity. Say, if you want to take out factor $2$ of $n$, you can choose $f(x)=x^2+2$ (although it's better if you don't use this method but instead removing all factors of $2$ before applying Pollard-Rho).

There are some odd prime factors you cannot find from your choice of polynomial $f(x)=x^2+1$. The algorithm fails to find prime divisor $p$ of $n$ when $p \nmid f(f(x))-f(x)$ for any $x$. In particular, this is equivalent to $p \nmid [(2x-1)^2+3][(2x+1)^2+3]$. According to Law of quadratic reciprocity, all primes $p$ so $p\equiv 5 \pmod{6}$ satisfies this condition. This follows the algorithm fails to factor primes $p \equiv 5 \pmod{6}$ out of $n$.

$\endgroup$
2
  • $\begingroup$ For perfect powers, it's not interesting to use Pollard's Rho because Pollard's Rho is sub-exponential while you can factor perfect powers in polynomial time --- $O( (\lg^3 n) \lg \lg \lg n)$. See note 3.6, chapter 3, in the Handbook of Applied Cryptography, pages 89--90. $\endgroup$
    – Joep Awinita
    Feb 13, 2019 at 18:17
  • $\begingroup$ This answer is wrong. If the offset $o$ in $f(x) = x^2 + o$ is odd, then the sequence of values generated by $f(x)$ simply alternates between even and odd integers. Depending on your starting value, the "hare" is always on even or always on odd integers, but the "tortoise" alternates between even and odd integers, leading to an even difference every second step. $\endgroup$
    – Kaspar Etter
    Sep 8, 2022 at 13:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .