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?

  • 0
    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.2012-10-16

0 Answers 0