For Wednesday:
- THERE WILL BE MODULE 3 ASSESSMENT in-class on MONDAY OCTOBER 10. The format will be similar to the previous assessment. Not explicitly cumulative beyond the necessary; we will still need basic facility with modular arithmetic and facts like Fermat’s little theorem etc. that we continue to use. I will update the list of topics to show what we have covered since the last module with red checkmarks.
- Compare the previous daily post to the solutions and learn from your mistakes.
- Factor $n=199163$ using the quadratic sieve method demonstrated in class. (You will also find some notes on Overleaf and in your textbook in the Factoring section (Sec 6.4.1 in 2nd ed).) You can use the Quadratic Sieve Tools page to produce the relations you will need. Hint on discord (I indicate a useful factor base, in case you are getting bogged down by too many primes).
- Suppose Eve listens in to an RSA session, so she knows Bob’s public key $(n,e)$ and the ciphertext $c$. Suppose she computes two lists: (a) a list of $c x^{-e} \pmod n$ for many small $x$; (b) a list of $y^e \pmod n$ for many small $y$.
-
- Explain how she can compute the message if she finds a collision between these two lists.
- How likely is a collision? What would have to be true about the message for a collision to happen?
-
- Write out a proof (I just appealed to your intuition in class), that if $x^2 \equiv y^2 \pmod{n}$ and $x \not\equiv \pm y \pmod{n}$, then $\gcd(x+y,n)$ is a proper (non-trivial, not $1$ or $n$) factor of $n$.