Exercise 2.4.14 (Pollard rho method)

Question

Use the Pollard rho method to locate proper divisors of the following numbers:
$$
\begin{array}{ll}
(a)\ 8,131; & (d)\ 16,019;\
(b)\ 7,913; & (e)\ 10,277;\
(c)\ 7,807; & (f)\ 199,934,971.
\end{array}
$$
}

Richard Ganaye · Accepted Answer

\begin{proof} The Pollard rho method in its simplest form gives the program 
\begin{verbatim}
from math import gcd

def rho_pollard(n):
    def f(x):
        return x*x+1
    x, y, d = 2, 2, 1
    while d==1:
        x = f(x) % n
        y = f(f(y)) % n
        d = gcd(x-y, n) 
    return d
\end{verbatim}

See \begin{verbatim} https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm \end{verbatim}

We obtain
\begin{align*}
\mathrm{rho\_pollard}(8131) &= 173,\qquad (8131 = 47 	imes 173),\
\mathrm{rho\_pollard}(7913) &= 41,\qquad\  (7913 = 41 	imes 193),\
\mathrm{rho\_pollard}(7807) &= 37,\qquad (7807 = 37 	imes 211),\
\mathrm{rho\_pollard}(16019) &= 83,\qquad (16019 = 83	imes 193),\
\mathrm{rho\_pollard}(10277) &= 43,\qquad (10277 = 43 	imes 239),\
\mathrm{rho\_pollard}(199934971) &= 16193,\qquad (199934971 = 12347	imes 16193).
\end{align*}
\end{proof}

Exercise 2.4.14 (Pollard rho method)

Answers

Comments

Exercise 2.4.14 (Pollard rho method)

Answers

Comments

Add answer