On the curve $y^2 = x^3 +2x + 1$ modulo 5, try to compute the addition of the two points P = (3,3) and Q = (1,2) by hand.
On the curve $y^2 = x^3 +2x + 1$ modulo 7, try to compute the addition of the two points P = (0,6) and Q = (0,1) by hand. The result should be the point at infinity (because these are inverses of each other), so the computation will “fail” — explain what fails that lets you know the result is the point at infinity.
On the curve $y^2 = x^3 +2x + 1$ modulo 35, try to compute the addition of the two points P = (28,13) and Q = (21,22) by hand. The result will fail. Explain why it fails and how it factors 35. Explain the relationship to the previous two problems.
Use EC Factoring Tools to factor n = 290265623. You might want to increase the size of the loop! Write up a short explanation of your work.
Write a small Sage for loop to implement Pollard p-1 factoring. Use it to factor n=16637. Some hints so you don’t get stuck:
remember to make $a$ into a value modulo $n$, for example with a = Mod(2,n) (it will actually work with integers but they grow so fast it isn’t efficient).
when you want to take a gcd of a value mod n, you need to make it an integer again by putting a ZZ around it, so like gcd(ZZ(a)-1,n).
start your loop at power 2 (squaring), not zero
If time remains, explore EC Factoring:
Do the example above again with a different choice of curve and point (revisit lecture for some advice on finding random curve + point pairs). Factor n.
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.
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.