Find the square root of $3$ modulo $p=11$ using the algorithm from the end of class. Now draw the dynamical portrait of powers of $3$ modulo $11$. Label each vertex as $3^x = y$ for whatever x and y, so each vertex can be interpreted as its value mod $p$ and its power of $3$. Can you use this diagram to explain why the method works?
Write a small for loop in sage that runs the Blum-Blum-Shub pseudo-random number generator.
Invent a way to check that the output “looks random”. Do you know a good statistical test? Or could you graph it somehow? If you discover some type of non-random-ish behaviour, it could lead to a way to factor integers!
Explain how, if you can factor $n$, you could find square roots modulo $n = pq$ where $p,q$ are primes congruent to $3$ modulo $4$. This is basically just recalling something we did in class.
Explain how, if you can find square roots modulo $n$, this allows you to factor $n$. (Find square roots means find all square roots.) This is basically just recalling something we did in class. This and the previous exercise show that factoring $n$ is considered equivalent to finding square roots modulo $n$.