Reminder: fill out the poster group form about poster groups (the link was in the last daily post).

Today’s lecture notes: Wednesday, September 23rd (also on the Notes/Videos page) — square roots and factoring, Miller-Rabin, Fermat factoring, and the quadratic sieve.

Friday’s lecture (September 25th) is pre-recorded and already up: the video and notes are on the Notes/Videos page.

Solution to the Kolmogorov complexity proof of the infinitude of primes (last daily post): it is written up in the textbook, Section 3.7 (Primality Testing).

Solutions: solutions to the daily posts due September 16th, 18th, 21st and 23rd are now posted (Sep 16, Sep 18, Sep 21, Sep 23). All daily post solutions are collected on the Archive page.

Relevant Textbook Sections:

3.7.2 (Miller-Rabin Primality Testing), 3.8 (Factoring), 3.8.3 (The role of squares in factoring), 3.8.4 (The quadratic sieve method), 3.6.3 (Short plaintext attack).

To Do:

1. Use the Miller-Rabin primality test with $a=2$ to determine if $n=90751$ is composite or probably prime. Show your steps.
2. If it comes up probably prime, try it with $a=3$. Show your steps.
3. Next, possibly using the Miller-Rabin Tools, implement the Miller-Rabin primality test to test if $n = 3057601$ is composite or probably prime, using the base $99908$.
4. Use Fermat Factoring to factor $n=16080$. Show the steps.
5. I wish to factor $n=38191$. How do I do it, if I have the following info?
   1. $196^2 - n$ factors as $3^2 \cdot 5^2$
   2. $201^2 - n$ factors as $2 \cdot 5 \cdot 13 \cdot 17$
   3. $214^2 - n$ factors as $3^2 \cdot 5 \cdot 13^2$
   4. $227^2 - n$ factors as $2 \cdot 3^3 \cdot 13 \cdot 19$
   5. $229^2 - n$ factors as $2 \cdot 3 \cdot 5^3 \cdot 19$
   6. $241^2 - n$ factors as $2 \cdot 3^2 \cdot 5 \cdot 13 \cdot 17$
   7. $254^2 - n$ factors as $3^4 \cdot 5^2 \cdot 13$
6. The euler-phi function gives $\varphi(21733) = 21420$. Use this fact to factor $21733$. (Hint: if $n=pq$, then knowing $n$ and $\varphi(n)$ tells you both $pq$ and $p+q$, so $p$ and $q$ are the two roots of a quadratic you can write down.)
7. Factor $n=31861$ using the Quadratic Sieve Tools page to produce the relations you will need. You may need to expand your factor base or the number of relations the boxes produce.
8. If you got lucky and got a single relation that did it, can you instead find a pair or larger combination of relations that do it?
9. Many of the messages posted on the #ciphertexts channel during the RSA ciphertext chain were pretty small. Can you attack any of them using the “small message” attack demonstrated in class (the birthday attack on RSA: look for a collision between $c x^{-e}$ and $y^e$, which reveals $m = xy$)? See also the textbook, Section 3.6.3 (Short plaintext attack).
10. Optional: If you aren’t familiar with for loops and if statements in Python/Sage, please visit these super quick tutorials: Python: For Loops and Python: If Statements. Then play around with the Sage Sandbox to see if you can find Carmichael numbers. This might require writing a for loop in python.

Added Sept 25: solutions to this daily post (Miller-Rabin, Fermat factoring, factoring from relations and from $\varphi(n)$, the quadratic sieve, the small-message attack, and Carmichael numbers) are now posted: Solutions to Daily Due Sep 25.