Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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$. – anon Oct 16 '12 at 19:32
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. – CodeKingPlusPlus Oct 16 '12 at 19:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.