Introduction to Cryptography with Coding Theory, 3rd Edition

21.7 Computer Problems

1. Let $E$ be the elliptic curve $y^2\equiv x^3+2x+3(\mathrm{m}\mathrm{o}\mathrm{d}19)\text{.}$

   1. Find the sum $(1\text{,}5)+(9\text{,}3)\text{.}$

   2. Find the sum $(9\text{,}3)+(9\text{,}-3)\text{.}$

   3. Using the result of part (b), find the difference $(1\text{,}5)-(9\text{,}3)\text{.}$

   4. Find an integer $k$ such that $k(1\text{,}5)=(9\text{,}3)\text{.}$

   5. Show that $(1\text{,}5)$ has exactly 20 distinct multiples, including $\text{∞}\text{.}$

   6. Using (e) and Exercise 19(d), show that the number of points on $E$ is a multiple of 20. Use Hasse’s theorem to show that $E$ has exactly 20 points.

2. You want to represent the message $12345$ as a point $(x\text{,}y)$ on the curve $y^2\equiv x^3+7x+11(\mathrm{m}\mathrm{o}\mathrm{d}593899)\text{.}$ Write $x=12345\mathrm{\_}$ and find a value of the missing last digit of $x$ such that there is a point on the curve with this $x\text{-coordinate}$.

3. 1. Factor 3900353 using elliptic curves.

   2. Try to factor 3900353 using the $p-$