This tool will quickly produce the iterates of a function: Pollard Rho. Use it to demonstrate the Pollard Rho factoring method on $n=4189$. You can use Sage to do your gcd’s, but make a nice little table on paper to demonstrate which gcd’s you are doing. If it doesn’t work, try modifying the function slightly (e.g. x^2-1) or the starting value, etc. (Pollard rho is a very flexible method.)
Use the birthday paradox approximation formula (with the natural log e in it) to determine the minimal number of people who need to be in the classroom to have at least a 50% chance of a shared birthday.
Discrete Log Review! Consider the discrete log problem $h = g^a$ modulo $p$. Suppose you make two lists: $g^x$ for random $x$ and $hg^{-y}$ for random $y$.
Explain how, if you get a collision, it results in a solution to the discrete log problem. This algorithm is called the “Birthday attack” on discrete log.
How long should you make these lists to expect a decent probability of a collision?
With reference to the last part, what is the runtime of the birthday attack on discrete log?
The Baby-Step-Giant-Step algorithm is a sort of “organized” birthday algorithm. Explain why I say this.
If time remains, a fun challenge: try to use the short message RSA attack discussed in class today on the short RSA message we had on discord (see the discord “ciphertexts” channel where I’ve pointed it out).