21.7 Computer Problems – Introduction to Cryptography with Coding Theory, 3rd Edition

21.7 Computer Problems

  1. Let E be the elliptic curve y2x3+2x+3(mod19).

    1. Find the sum (1, 5)+(9, 3).

    2. Find the sum (9, 3)+(9, 3).

    3. Using the result of part (b), find the difference (1, 5)(9, 3).

    4. Find an integer k such that k(1, 5)=(9, 3).

    5. Show that (1, 5) has exactly 20 distinct multiples, including .

    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, y) on the curve y2x3+7x+11(mod593899). Write x=12345_ and find a value of the missing last digit of x such that there is a point on the curve with this x-coordinate.

    1. Factor 3900353 using elliptic curves.

    2. Try to factor 3900353 using the p1 method