Reminder: Class on Wednesday, October 21st is on Zoom. The link is in Canvas. If you need a quiet place to join, you are welcome to use our usual classroom. The class will be recorded, but please attend synchronously if you can.

Solutions: solutions to the daily posts due October 16th (elliptic curve multiples table) and October 19th (EC El Gamal chain and Pollard $p-1$) are posted. All daily post solutions are collected on the Archive page.

Relevant Textbook Sections:

5.4 (Factoring with elliptic curves), including 5.4.1 (An example motivating the key idea), 5.4.2 (Pollard’s $p-1$ factoring algorithm) and 5.4.3 (Elliptic Curve Factoring). Review 3.8.1 (Pollard’s rho factoring method).

To Do:

1. Finish up the Elliptic Curve El Gamal ciphertext chain from last time: make sure you have decrypted any message encrypted to your public key (and announced the plaintext, @mentioning the sender), that your own message has been decrypted and confirmed, and that your notes are handed in to the canvas dropbox.
2. On the curve $y^2 = x^3 + x + 1$ modulo $91$, check that $P = (0,1)$ and $Q = (7,13)$ are on the curve, and then try to compute $P + Q$ by hand. What goes wrong when you compute the slope? Use the failure to factor $91$. Then reduce $P$ and $Q$ modulo each prime factor of $91$: what is $P + Q$ modulo each prime? Explain why the computation broke down.
3. Use the EC Factoring Example page to factor $n = 290265623$. You might want to increase the size of the loop! Write up a short explanation of your work.
4. A factoring race. We now have three factoring methods that each look for a prime factor $p$ of $n$ “by accident.” Run all three on the same $n = 290265623$ from problem 3 and record how long each one takes:
   1. Pollard’s $\rho$ with $f(x) = x^2 + 1$ and $x_0 = 2$: how many steps until $\gcd(x_{2i} - x_i, n)$ is nontrivial? ($n$ is too big for the Pollard Rho Demo, so use the Sage Pollard Rho page, which keeps a tortoise and a rabbit and prints the gcd at each step.)
   2. Pollard’s $p-1$ with $a = 2$ (use the Pollard p-1 page from last time): what is the first $B$ for which $\gcd(a^{B!}-1, n)$ is nontrivial? Again, you may need to increase the size of the loop.
   3. Elliptic curve factoring (problem 3; you already did this): which multiple blew up?
5. Now factor $p - 1$ for each prime factor $p$ of $n$ from the last problem. Use this to explain the $p-1$ result exactly.
6. Recall that Pollard’s $\rho$ takes about $\sqrt{p}$ steps. Compare $\sqrt{p}$ with your step count from problem 4.
7. In Sage, EllipticCurve(GF(p), [1,1])(0,1).order() computes the order of the point $(0,1)$ on $y^2 = x^3 + x + 1$ modulo a prime $p$ (change the coefficients and the point if you used a different curve in problem 3). Compute this order modulo each prime factor of $n$, and factor the answers. Use this to explain which multiple blew up in problem 3.
8. For which kinds of $n$ would you choose $\rho$, which $p-1$, and which elliptic curves?
9. If time remains, explore EC Factoring further:
   1. Factor $n = 290265623$ again with a different choice of curve and point (revisit lecture for some advice on finding random curve + point pairs).
   2. Try modifying one of the middle digits of $n$, and see how long it takes. Factor $n$ completely using Sage’s factor() function, to see what kinds of primes it has in it. Repeat a few more times.
   3. Report/discuss on discord on how long it took (i.e., what multiple of $P$ blew up) on different curves and points, and different $n$. Explain why you think it was fast sometimes and slow other times. You can use the #daily-collaboration channel.