2.4: Problem 14: Use Pollard rho method to locate proper divisors of the following numbers: (a) \(8,131\)
Solution
Use the polynomial \(f(x) = x^2 + 1\). Let \(u_1 = 2\), we generate more numbers modulo \(8131\) as follows
$$
\begin{align*}
u_2 &= f(u_1) = 5 \\
u_3 &= f(5) = 26 \\
u_4 &= f(26) = 677 \\
u_5 &= f(677) = 458,330 \pmod{8131} = 2994 \\
u_6 &= f(2994) = 8,964,037 \pmod{8131} = 3675 \\
u_7 &= f(3675) = 13,505,626 \pmod{8131} = 35 \\
u_8 &= f(35) = 1,226 \pmod{8131} = 1226 \\
u_9 &= f(1226) = 1,503,077 \pmod{8131} = 6,973 \\
u_{10} &= f(6973) = 48,622,730 \pmod{8131} = 7,481 \\
u_{11} &= f(7481) = 55,965,362 \pmod{8131} = 7,820 \\
u_{12} &= f(7820) = 61,152,401 \pmod{8131} = 7,281 \\
u_{13} &= 6,973 \\
u_{14} &= 7,481 \\
u_{15} &= 7,820 \\
u_{16} &= 7,281
\end{align*}
$$
Now, we compute the gcd of \(u_i\) and \(u_{2i}\) and check if it satisfies \(1 < \gcd < 8131\)
$$
\begin{align*}
\gcd(u_2-u_1, 8131) &= \gcd(3, 8131) = 1 \\
\gcd(u_4-u_2, 8131) &= \gcd(672, 8131) = 1 \\
\gcd(u_6-u_3, 8131) &= \gcd(3649, 8131) = 1 \\
\gcd(u_8-u_4, 8131) &= \gcd(549, 8131) = 1 \\
\gcd(u_{10}-u_5, 8131) &= \gcd(4487, 8131) = 1 \\
\gcd(u_{12}-u_6, 8131) &= \gcd(3606, 8131) = 1 \\
\gcd(u_{14}-u_7, 8131) &= \gcd(7446, 8131) = 1 \\
\gcd(u_{16}-u_8, 8131) &= \gcd(6055, 8131) = 173
\end{align*}
$$
\(173\) is indeed a divisor of \(8131\). In fact, \(8131 \div 173 = 47\).