Solutions: solutions to the daily post due October 14th (projective space) are posted. All daily post solutions are collected on the Archive page.

Test 2 solutions: Test 2 (Module 2) with solutions are posted (also linked from the Tests tab).

Tools: if you want more practice adding points by hand, the Practice Problems page makes random elliptic curve addition problems, and the Elliptic Curve Tools page and the Elliptic Curve Playground will check your work.

Relevant Textbook Sections:

5.5 (Elliptic Curve Discrete Logarithm Problem).

To Do:

On the elliptic curve $E: y^2 = x^3 + x + 1$ modulo $11$, take $P = (1,5)$. Its multiples are:

$k$	$kP$	$k$	$kP$
$1$	$(1,5)$	$8$	$(0,1)$
$2$	$(3,3)$	$9$	$(4,5)$
$3$	$(8,2)$	$10$	$(6,6)$
$4$	$(6,5)$	$11$	$(8,9)$
$5$	$(4,6)$	$12$	$(3,8)$
$6$	$(0,10)$	$13$	$(1,6)$
$7$	$(2,0)$	$14$	$\infty$

Every point of $E$ appears in this table. Use it for all the problems below.

1. How many points does $E$ have? Check that this satisfies Hasse’s bound.
2. If you have an elliptic curve modulo $13$, what is the maximum and minimum number of points it could have?
3. Using only the table (no slopes!), compute $(3,3) + (8,9)$ and $(6,5) + (6,5)$.
4. Using the table, find $-(4,6)$. Check that it agrees with what you know about negating a point geometrically.
5. What is the order of $7P = (2,0)$? Connect this to problem 5 from the daily post due October 12th. Which points of $E$ have order $7$? Which have order $14$?
6. (ECDLP) Find $k$ such that $kP = (6,6)$. The table makes this a lookup. Explain why, for a curve modulo a $256$-bit prime, nobody can write down this table, and why being able to compute any single $kP$ quickly (by double-and-add) doesn’t help you solve for $k$.
7. In the next class, we’ll define Elliptic Curve Diffie Hellman. But in class today, I already explained how the work we did in the first unit has an analogue for an elliptic curve. So you can already define this yourself! Write down what should be the Elliptic Curve Diffie Hellman protocol, and bring it to class to compare to what we do.