Reminder: Test 2 (Module 2) is in class this Wednesday, October 7th (full period). The syllabus and review problems are on the Tests tab.

Test 1 solutions: Test 1 (Module 1) with solutions are posted (also linked from the Tests tab).

New tool: the Pollard Rho Demo page walks through Pollard’s $\rho$ method one step at a time: the tortoise-and-rabbit table from class, the $\rho$-shaped picture of the sequence, and (behind the scenes) what happens modulo each prime factor.

Relevant Textbook Sections:

3.8.1 (Pollard’s rho factoring method).

To Do:

1. Use Pollard’s rho method with $f(x) = x^2 + 1$ and $x_0 = 2$ to factor $n = 8051$. You may use the Pollard Rho page or the Sage Sandbox for the arithmetic. Afterwards, check your table against the Pollard Rho Demo (it has $8051$ as a preset), and look at its pictures modulo $83$ and $97$: why did the method find $97$ and not $83$? Then try $n = 10403$ and $n = 455459$ on that page.
2. Explain, using the birthday paradox, why Pollard’s rho typically finds a prime factor $p$ of $n$ after about $\sqrt{p}$ steps. (Hint: the sequence $x_i \bmod p$ behaves like random values modulo $p$, and you are waiting for a collision modulo $p$.) If $n$ is an RSA modulus with two $100$-digit prime factors, about how many steps is that?