2
$\begingroup$

I am trying to better understand the ideas and intuition behind the Pollard Rho factorization algorithms.

Given an $x_0$ and an irreducibe polynomial we can create a sequence from the recursive definition:

$x_i \equiv f(x_{i-1}) \mod n$

Let $y_i = x_i \mod d$

The book I am reading then states: Since

$x_i \equiv f(x_{i-1}) \mod n$ then

$y_i \equiv f(y_{i-1}) \mod d$

Why does the change in modulus preserve the relationship $x_i \equiv f(x_{i-1})$?

I am starting to see that since $y_i$ is $x_i$ then the same function with $f(y_{i-1})$ so it is just the same numbers with a different modulus. Is this correct? Is there a better or more formal way to see this?

$\endgroup$
2
  • $\begingroup$ I assume $d\mid n$? There is a surjective map $\Bbb Z/n\Bbb Z\to\Bbb Z/d\,\Bbb Z$ for any $d\mid n$ given by simply "copy and pasting" integer representatives. This is well-defined since $a\equiv b$ mod $n$ implies $n\mid (a-b)$ implies $d\mid (a-b)$ implies $a\equiv b$ mod $d$. $\endgroup$
    – anon
    Oct 16, 2012 at 19:32
  • $\begingroup$ The goal is to find this $d$ so that some $x_i \equiv x_j \mod d$ and then conclude that when $x_i \neq x_j$ then $\gcd(n, x_i - x_j)$ is non-trivial. $\endgroup$ Oct 16, 2012 at 19:44

0

You must log in to answer this question.