Factorize the natural number $n$ with the method $\rho$-rho of Pollard

62 Views Asked by At

I want to factorize the natural number $n=32437$ with the method $\rho$-rho of Pollard.

$$$$

I have done the following:

Let's consider $x=y=2$ ($x_1=y_1=2$) and $c=1$. We have then $f(x)=x^2+c=x^2+1$.

Then:

\begin{equation*}\begin{matrix}x_{i+1}=f(x_i)\bmod n & y_{i+1}=f(f(y_i))\bmod n & c & d=gcd (|x_{i+1}-y_{i+1}|, n) \\ 5 & 26 & 1 & 1 \\ 26 & 4212 & 1 & 1 \\ 677 & 5842 & 1 & 1 \\ 4212 & 26380 & 1 & 163 \neq 1, n \end{matrix}\end{equation*}

Since the last gcd is neither equal to $1$ nor equal to $n$, this number is a factor of $n$. The other factor is $\frac{n}{163}=199$.

$$$$

Is everything correct? Have I applied correctly the method? t the end can I just say that the other facto is $\frac{n}{163}$ ?