1. Let $x^3+a{x}^2+bx+c$ be a cubic polynomial with roots $r_1\text{,}{r}_2\text{,}{r}_3\text{.}$ Show that $r_1+r_2+r_3=-a\text{.}$

2. Write $x=x_1-a/3\text{.}$ Show that

   $$x^3+a{x}^2+bx+c=x_1^3+b^{\prime }{x}_1+c^{\prime }\text{,}$$

   with $b^{\prime }=b-(1/3)a^2$ and $c^{\prime }=c-(1/3)ab+(2/27)a^3\text{.}$ (Remark: This shows that a simple change of variables allows us to consider the case where the coefficient of $x^2$ is 0.)

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

1. List the points on $E$ (don’t forget $\text{∞}$).

2. Evaluate the elliptic curve addition $(2\text{,}0)+(4\text{,}3)\text{.}$

1. List the points on the elliptic curve $E:y^2\equiv x^3-2(\mathrm{m}\mathrm{o}\mathrm{d}7)\text{.}$

2. Find the sum $(3\text{,}2)+(5\text{,}5)$ on $E\text{.}$

3. Find the sum $(3\text{,}2)+(3\text{,}2)$ on $E\text{.}$

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

1. Evaluate $(1\text{,}2)+(2\text{,}5)\text{.}$

2. Evaluate $2(1\text{,}2)\text{.}$

3. Evaluate $(1\text{,}2)+\text{∞}\text{.}$

1. Find the sum of the points (1, 2) and (6,3) on the elliptic curve $y^2\equiv x^3+3(\mathrm{m}\mathrm{o}\mathrm{d}7)\text{.}$

2. Eve tries to find the sum of the points (1,2) and (6,3) on the elliptic curve $y^2\equiv x^3+3(\mathrm{m}\mathrm{o}\mathrm{d}35)\text{.}$ What information does she obtain?

Show that if $P=(x\text{,}0)$ is a point on an elliptic curve, then $2P=\text{∞}\text{.}$

Find an elliptic curve mod 101 such that $(43\text{,}21)$ is a point on the curve.

The point $(3\text{,}5)$ lies on the elliptic curve $y^2=x^3-2$ defined over the rational numbers. use the addition law to find another point with positive rational coordinates that lies on this curve.

1. Show that $Q=(2\text{,}3)$ on $y^2=x^3+1$ satisfies $6Q=\text{∞}\text{.}$ (Hint: Compute $3Q\text{,}$ then use Exercise 6.)

2. Your computations in (a) probably have shown that $2Q\ne \text{∞}$ and $3Q\ne \text{∞}\text{.}$ Use this to show that the points $\text{∞}\text{,}Q\text{,}2Q\text{,}3Q\text{,}4Q\text{,}5Q$ are distinct.

1. Factor $n=35$ by the elliptic curve method by using the elliptic curve $y^2\equiv x^3+26$ and calculating 3 times the point $P=(10\text{,}9)\text{.}$

2. Factor $n=35$ by the elliptic curve method by using the elliptic curve $y^2\equiv x^3+5x+8$ and the point $P=(1\text{,}28)\text{.}$

Suppose you want to factor a composite integer $n$ by using the elliptic curve method. You start with the curve $y^2=x^3-4x(\mathrm{m}\mathrm{o}\mathrm{d}n)$ and the point $(2\text{,}0)\text{.}$ Why will this not yield the factorization of $n$?

Devise an analog of the procedure in Exercise 11(a) in Chapter 10 that uses elliptic curves.

Let $p=999983\text{.}$ The elliptic curve $E:y^2\equiv x^3+1(\mathrm{m}\mathrm{o}\mathrm{d}p)$ has 999984 points. Suppose you are given points $P$ and $Q$ on $E$ and are told that there is an integer $k$ such that $Q=kP\text{.}$

1. Describe a birthday attack that is expected to find $k\text{.}$

2. Describe how the Baby Step, Giant Step method (see Section 10.2) finds $k\text{.}$

Let $P$ and $Q$ be points on an elliptic curve $E\text{.}$ Peggy claims that she knows an integer $k$ such that $kP=Q$ and she wants to convince Victor that she knows $k$ without giving Victor any information about $k\text{.}$ They perform a zero-knowledge protocol. The first step is the following:

1. Peggy chooses a random integer $r_1$ and lets $r_2=k-r_1\text{.}$ She computes $X_1=r_{1}P$ and $X_2=r_{2}P$ and sends them to Victor.

   Give the remaining steps. Victor wants to be at least $99\%$ sure that Peggy knows $k\text{.}$ (Technical note: You may regard $r_1$ and $r_2$ as numbers mod $n\text{,}$ where $nP=\text{∞}\text{.}$ Without congruences, Victor obtains some information about the size of $k\text{.}$

   Nontechnical note: The “Technical note” may be ignored when solving the problem.)

Find all values of $y$ mod 35 such that $(1\text{,}y)$ is a point on the curve $y^2\equiv x^3+3x+12(\mathrm{m}\mathrm{o}\mathrm{d}35)\text{.}$

Suppose $n$ is a product of two large primes and let $E:y^2\equiv x^3+bx+c(\mathrm{m}\mathrm{o}\mathrm{d}n)\text{.}$ Bob wants to find some points on $E\text{.}$

1. Bob tries choosing a random $x\text{,}$ computing $x^3+bx+c\text{,}$ and finding the square root of this number mod $n\text{,}$ when the square root exists. Why will this strategy probably fail if Bob does not know $p$ and $q$?

2. Suppose Bob knows $p$ and $q\text{.}$ Explain how Bob can use the method of part (a) successfully? (Hint: He needs to use the Chinese Remainder Theorem.)

Show that if $P\text{,}Q\text{,}R$ are points on an elliptic curve, then

1. Eve is trying to find an elliptic curve discrete log: She has points $A$ and $B$ on an elliptic curve $E$ such that $B=kA$ for some $k\text{.}$ There are approximately ${10}^{20}$ points on $E\text{,}$ so assume that $1\le k\le {10}^{20}\text{.}$ She makes two lists and looks for a match. The first list is $jA$ for $N$ randomly chosen values of $j\text{.}$ The second is $B-\mathrm{\ell }A$ for $N$ randomly chosen values of $\mathrm{\ell }\text{.}$ How big should $N$ be so that there is a good chance of a match?

2. Give a classical (that is, not elliptic curve) version of the procedure in part (a).

Let $P$ be a point on the elliptic curve $E$ mod a prime $p\text{.}$

1. Show that there are only finitely many points on $E\text{,}$ so $P$ has only finitely many distinct multiples.

2. Show that there are integers $i\text{,}j$ with $i>j$ such that $iP=jP\text{.}$ Conclude that $(i-j)P=\text{∞}\text{.}$

3. The smallest positive integer $k$ such that $kP=\text{∞}$ is called the order of $P\text{.}$ Let $m$ be an integer such that $mP=\text{∞}\text{.}$ Show that $k$ divides $m\text{.}$ (Hint: Imitate the proof of Exercise 53(c, d) in Chapter 3.)

4. (for those who know some group theory) Use Lagrange’s theorem from group theory to show that the number of points on $E$ is a multiple of the order of $P\text{.}$ (Combined with Hasse’s theorem, this gives a way of finding the number of points on $E\text{.}$ See Computer Problems 1 and 4.)

Let $P$ be a point on the elliptic curve $E\text{.}$ Suppose you know a positive integer $k$ such that $kP=\text{∞}\text{.}$ You want to prove (or disprove) that $k$ is the order of $P\text{.}$

1. Show that if $(k/p)P=\text{∞}$ for some prime factor $p$ of $k\text{,}$ then $k$ is not the order of $P\text{.}$

2. Suppose $m|k$ and $1\le m<k\text{.}$ Show that $m|(k/p)$ for some prime divisor $p$ of $k\text{.}$

3. Suppose that $(k/p)P\ne \text{∞}$ for each prime factor of $k\text{.}$ Use Exercise 11(c) to show that the order of $P$ is $k\text{.}$ (Compare with Exercise 54 in Chapter 3. For an example, see Computer Problem 4.)

1. Let $x=b_1{b}_2\dots b_w$ be an integer written in binary. Let $P$ be a point on the elliptic curve $E\text{.}$ Perform the following procedure:

   1. Start with $k=1$ and $S_1=\text{∞}\text{.}$

   2. If $b_k=1\text{,}$ let $R_k=S_k+P\text{.}$ If $b_k=0\text{,}$ let $R_k=S_k\text{.}$

   3. Let $S_{k+1}=2R_k\text{.}$

   4. If $k=w\text{,}$ stop. If $k<w\text{,}$ add 1 to $k$ and go to step 2.

   Show that $R_w=xP\text{.}$ (Compare with Exercise 56(a) in Chapter 3.)

2. Let $x$ be a positive integer and let $P$ be a point on an elliptic curve. Show that the following procedure computes $xP\text{.}$

   1. Start with $a=x\text{,}B=\text{∞}\text{,}C=P\text{.}$

   2. If $a$ is even, let $a=a/2\text{,}$ and let $B=B\text{,}C=2C\text{.}$

   3. If $a$ is odd, let $a=a-1\text{,}$ and let $B=B+C\text{,}C=C\text{.}$

   4. If $a\ne 0\text{,}$ go to step 2.

   5. Output $B\text{.}$

   (Compare with Exercise 56(b) in Chapter 3.)

Let $E$ be an elliptic curve mod $n$ (where $n$ is some integer) and let $P$ and $Q$ be points on $E$ with $2P=Q\text{.}$ The curve $E$ and the point $Q$ are public and are known to everyone. The point $P$ is secret. Peggy wants to convince Victor that she knows $P\text{.}$ They do the following procedure:

1. Peggy chooses a random point $R_1$ on $E$ and lets $R_2=P-R_1\text{.}$

2. Peggy computes $H_1=2R_1$ and $H_2=2R_2$ and sends $H_1\text{,}{H}_2$ to Victor.

3. Victor checks that $H_1+H_2=Q\text{.}$

4. Victor makes a request and Peggy responds.

5. Victor now does something else.

6. They repeat steps 1 through 5 several times.

1. Describe what is done in steps 4 and 5.

2. Give a classical (non-elliptic curve) version of this protocol that yields a zero-knowledge proof that Peggy knows a solution $x$ to $x^2\equiv s\mathrm{m}\mathrm{o}\mathrm{d}n\text{.}$

Let $E$ be an elliptic curve mod a large prime, let $N$ be the number of points on $E\text{,}$ and let $P$ and $Q$ be points on $E\text{.}$ Peggy claims to know an integer $s$ such that $sP=Q\text{.}$ She wants to prove this to Victor by the following procedure. Victor knows $E\text{,}$ $P\text{,}$ and $Q\text{,}$ but he does not know $s$ and should receive no information about $s\text{.}$

1. Peggy chooses a random integer $r_1$ mod $N$ and lets $r_2\equiv s-r_1(\mathrm{m}\mathrm{o}\mathrm{d}N)\text{.}$ (Don’t worry about why it’s mod $N\text{.}$ It’s for technical reasons.)

2. Peggy computes $Y_1=r_{1}P$ and $Y_2=r_{2}P$ and sends $Y_1$ and $Y_2$ to Victor.

3. Victor checks something.

4. Victor randomly chooses $i=1$ or $2$ and asks Peggy for $r_i\text{.}$

5. Peggy sends $r_i$ to Victor.

6. Victor checks something.

7. Step (7).

1. What does Victor check in step (3)?

2. What does Victor check in step (6)?

3. What should step (7) be if Victor wants to be at least $99.9\%$ sure that Peggy knows $s$?

Here is an elliptic curve version of the Digital Signature Algorithm. Alice wants to sign a message $m\text{,}$ which is an integer. She chooses a prime $p$ and an elliptic curve $E(\mathrm{m}\mathrm{o}\mathrm{d}p)\text{.}$ The number of points $n$ on $E$ is computed and a large prime factor $q$ of $n$ is found. A point $A(\ne \text{∞})$ is chosen such that $qA=\text{∞}\text{.}$ (In fact, $n$ is not needed. Choose a point $A^{\prime }$ on $E$ and find an integer $n^{\prime }$ with $n^{\prime }{A}^{\prime }=\text{∞}\text{.}$ There are ways of doing this, though it is not easy. Let $q$ be a large prime factor of $n^{\prime }\text{,}$ if it exists, and let $A=(n^{\prime }/q)A^{\prime }\text{.}$ Then $qA=\text{∞}\text{.}$) It is assumed that the message satisfies $0\le m<q\text{.}$ Alice chooses her secret integer $a$ and computes $B=aA\text{.}$ The public information is $p\text{,}E\text{,}q\text{,}A\text{,}B\text{.}$ Alice does the following:

1. Chooses a random integer $k$ with $1\le k<q$ and computes $R=kA=(x\text{,}y)$

2. Computes $s\equiv k^{-1}(m+ax)(\mathrm{m}\mathrm{o}\mathrm{d}q)$

3. Sends the signed message $(m\text{,}R\text{,}s)$ to Bob

Bob verifies the signature as follows:

1. Computes $u_1\equiv s^{-1}m(\mathrm{m}\mathrm{o}\mathrm{d}q)$ and $u_2\equiv s^{-1}x(\mathrm{m}\mathrm{o}\mathrm{d}q)$

2. Computes $V=u_{1}A+u_{2}B$

3. Declares the signature valid if $V=R$

1. Show that the verification equation holds for a correctly signed message. Where is the fact that $qA=\text{∞}$ used (see the “subtle point” mentioned in the ElGamal scheme in Section 21.5)?

2. Why does $k^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}q)$ exist?

3. If $q$ is large, why is there very little chance that $s^{-1}$ does not exist mod $q$? How do we recognize the case when it doesn’t exist? (Of course, in this case, Alice should start over by choosing a new $k\text{.}$)

4. How many computations “(large integer)$\times$(point on $E$)” are made in the verification process here? How many are made in the verification process for the elliptic ElGamal scheme described in the text? (Compare with the end of Section 13.5.)

Let $A$ and $B$ be points on an elliptic curve and suppose $B=kA$ for some integer $k\text{.}$ Suppose also that $2^{n}A=\text{∞}$ for some integer $n\text{,}$ but $T=2^{n-1}A\ne \text{∞}\text{.}$

1. Show that if $k\equiv k^{\prime }(\mathrm{m}\mathrm{o}\mathrm{d}{2}^n)\text{,}$ then $B=k^{\prime }A\text{.}$ Therefore, we may assume that $0\le k<2^n\text{.}$

2. Let $j$ be an integer. Show that $jT=\text{∞}$ when $j$ is even and $jT\ne \text{∞}$ when $j$ is odd.

3. Write $k=x_0+2x_1+4x_2+\cdots +2^{n-1}{x}_{n-1}\text{,}$ where each $x_i$ is 0 or 1 (binary expansion of $k$). Show that $x_0=0$ if and only if $2^{n-1}B=\text{∞}\text{.}$

4. Suppose that for some $m<n$ we know $x_0\text{,}\dots \text{,}{x}_{m-1}\text{.}$ Let $Q_m=B-(x_0+\cdots +2^{m-1}{x}_{m-1})A\text{.}$ Show that $2^{n-m-1}{Q}_m=\text{∞}$ if and only if $x_m=0\text{.}$ This allows us to find $x_m\text{.}$ Continuing in this way, we obtain $x_0\text{,}\dots \text{,}{x}_{n-1}\text{,}$ and therefore we can compute $k\text{.}$ This technique can be extended to the case where $sA=\text{∞}\text{,}$ where $s$ is an integer with only small prime factors. This is the analog of the Pohlig-Hellman algorithm (see Section 10.2).