All of the elliptic curves we work with in this chapter are elliptic curves $\text{mod }n$. However, it is helpful to use the graphs of elliptic curves with real numbers in order to visualize what is happening with the addition law, for example, even though such pictures do not exist $\text{mod }n$. Therefore, let’s graph the elliptic curve $y^2=x(x-1)(x+1)$. We’ll specify that $-1\le x\le 3$ and $-y\le y\le 5$:

In[1]:= ContourPlot[$\mathrm{y}\widehat{\phantom{\mathrm{a}}}2$ == x*(x - 1)*(x + 1), {x, -1, 3 }, {y, -5, 5 }]

Graphics

Add the points (1, 3) and (3, 5) on the elliptic curve $y^2\equiv x^3+24x+13(\text{mod}29)$.

In[2]:= addell[ {1, 3 }, {3, 5 }, 24, 13, 29]

Out[2]= {26, 1 }

You can check that the point (26, 1) is on the curve: ${26}^3+24\cdot 26+13\equiv 1^2(\text{mod}29)$.

Add (1, 3) to the point at infinity on the curve of the previous example.

In[3]:= addell[ {1, 3 }, {”infinity”, ”infinity” }, 24, 13, 29]

Out[3]= {1, 3 }

As expected, adding the point at infinity to a point $P$ returns the point $P$.

Let $P=(1\text{,}3)$ be a point on the elliptic curve $y^2\equiv x^3+24x+13(\text{mod}29)$. Find $7P$.

In[4]:= multell[ {1, 3 }, 7, 24, 13, 29]

Out[4]= {15, 6 }

Find $k(1\text{,}3)$ for $k=1\text{,}2\text{,}3\text{,}\dots \text{,}40$ on the curve of the previous example.

In[5]:= multsell[ {1, 3 }, 40, 24, 13, 29]

Out[5]= {1,{1,3},2,{11,10},3,{23,28},4,{0,10},5,{19,7},6,{18,19},7, {15,6},8,{20,24},9,{4,12},10,{4,17},11,{20,5},12,{15,23},13,{18,10}, 14,{19,22},15,{0,19}, 16,{23,1},17,{11,19},18,{1,26},19, {infinity,infinity},20,{1,3},21,{11,10}, 22,{23,28},23,{0,10}, 24,{19,7}, 25,{18,19},26,{15,6},27,{20,24},28,{4,12},29,{4,17}, 30,{20,5},31,{15,23},32,{18,10},33,{19,22}, 34,{0,19},35,{23,1},36, {11,19},37,{1,26}, 38,{infinity,infinity},39,{1,3},40,{11,10}}

Notice how the points repeat after every 19 multiples.

The previous four examples worked mod the prime 29. If we work mod a composite number, the situation at infinity becomes more complicated since we could be at infinity mod both factors or we could be at infinity mod one of the factors but not mod the other. Therefore, we stop the calculation if this last situation happens and we exhibit a factor. For example, let’s try to compute $12P$, where $P=(1\text{,}3)$ is on the elliptic curve $y^2\equiv x^3-5x+13(\text{mod}209)$:

In[6]:= multell[ {1, 3 }, 12, -5, 13, 11*19]

Out[6]= {factor=, 19 }

Now let’s compute the successive multiples to see what happened along the way:

In[7]:= multsell[ {1, 3 }, 12, -5, 13, 11*19]

Out[7]= 1,{{1,3},2,{91,27},3,{118,133},4,{148,182},5,{20,35}, 6,{factor=, 19}}

When we computed $6P$, we ended up at infinity mod 19. Let’s see what is happening mod the two prime factors of 209, namely 19 and 11:

In[8]:= multsell[{1,3}, 12, -5, 13, 19]

Out[8]= 1,{{1,3},2,{15,8},3,{4,0},4,{15,11},5,{1,16}, 6,{infinity,infinity}, 7,{1,3},8,{15,8},9,{4,0},10,{15,11}, 11,{1,16}, 12,{infinity,infinity}}

In[9]:= multsell[ {1, 3 }, 20, -5, 13, 11]

Out[9]= 1,{{1,3},2,{3,5},3,{8,1},4,{5,6},5,{9,2},6,{6,10},7,{2,0}, 8,{6,1},9,{9,9},10,{5,5},11,{8,10},12,{3,6},13,{1,8}, 14,{infinity,infinity},15,{1,3}, 16,{3,5},17,{8,1},18,{5,6}, 19,{9,2},20,{6,10}}

After six steps, we were at infinity mod 19, but it takes 14 steps to reach infinity mod 11. To find $6P$, we needed to invert a number that was 0 mod 19 and nonzero mod 11. This couldn’t be done, but it yielded the factor 19. This is the basis of the elliptic curve factorization method.

Factor 193279 using elliptic curves.

SOLUTION

First, we need to choose some random elliptic curves and a point on each curve. For example, let’s take $P=(2\text{,}4)$ and the elliptic curve

For $P$ to lie on the curve, we take $b=28$. We’ll also take

Now we compute multiples of the point $P$. We do the analog of the $p-1$ method, so we choose a bound $B$, say $B=12$, and compute $B!P$.

In[10]:= multell[{2,4}, Factorial[12], -10, 28, 193279]

Out[10]= {factor=, 347}

In[11]:= multell[{1,1}, Factorial[12], 11, -11, 193279]

Out[11]= {13862, 35249}

In[12]:= multell[{1, 2}, Factorial[12], 17, -14, 193279]

Out[12]= {factor=, 557}

Let’s analyze in more detail what happened in these examples.

On the first curve, $266P$ ends up at infinity mod 557 and $35P$ is infinity mod 347. Since $266=2\cdot 7\cdot 19$, it has a prime factor larger than $B=12$, so $B!P$ is not infinity mod 557. But 35 divides $B!$, so $B!P$ is infinity mod 347.

On the second curve, $356P=\text{infinity}$ mod 347 and $561P=\text{infinity}$ mod 557. Since $356=4\cdot 89$ and $561=3\cdot 11\cdot 17$, we don’t expect to find the factorization with this curve.

The third curve is a surprise. We have $331P=\text{infinity}$ mod 347 and $272P=\text{infinity}$ mod 557. Since $331$ is prime and $272=16\cdot 17$, we don’t expect to find the factorization with this curve. However, by chance, an intermediate step in the calculation of $B!P$ yielded the factorization. Here’s what happened. At one step, the program required adding the points (184993, 13462) and (20678, 150484). These two points are congruent mod 557 but not mod 347. Therefore, the slope of the line through these two points is defined mod 347 but is 0/0 mod 557. When we tried to find the multiplicative inverse of the denominator mod 193279, the gcd algorithm yielded the factor 557. This phenomenon is fairly rare.

Here is how to produce the example of an elliptic curve ElGamal cryptosystem from Section 21.5. For more details, see the text. The elliptic curve is $y^2\equiv x^3+3x+45(\text{mod}8831)$ and the point is $G=(4\text{,}11)$. Alice’s message is the point $P_m=(5\text{,}1743)$.

Bob has chosen his secret random number $a_B=3$ and has computed $a_{B}G$:

In[13]:= multell[{4, 11}, 3, 3, 45, 8831]

Out[13]= {413, 1808}

Bob publishes this point. Alice chooses the random number $k=8$ and computes $kG$ and $P_m+k(a_{B}G)$:

In[14]:= multell[{4, 11}, 8, 3, 45, 8831]

Out[14]= {5415, 6321}

In[15]:= addell[{5, 1743}, multell[{413, 1808}, 8, 3, 45, 8831], 3, 45, 8831]

Out[15]= {6626, 3576}

Alice sends (5415, 6321) and (6626, 3576) to Bob, who multiplies the first of these points by $a_B$:

In[16]:= multell[{5415, 6321}, 3, 3, 45, 8831]

Out[16]= {673, 146}

Bob then subtracts the result from the last point Alice sends him. Note that he subtracts by adding the point with the second coordinate negated:

In[17]:= addell[{6626, 3576}, {673, -146}, 3, 45, 8831]

Out[17]= {5, 1743}

Bob has therefore received Alice’s message.

Let’s reproduce the numbers in the example of a Diffie-Hellman key exchange from Section 21.5: The elliptic curve is $y^2\equiv x^3+x+7206(\text{mod}7211)$ and the point is $G=(3\text{,}5)$. Alice chooses her secret $N_A=12$ and Bob chooses his secret $N_B=23$. Alice calculates

In[18]:= multell[{3, 5}, 12, 1, 7206, 7211]

Out[18]= {1794, 6375}

She sends (1794,6375) to Bob. Meanwhile, Bob calculates

In[19]:= multell[{3, 5}, 23, 1, 7206, 7211]

Out[19]= {3861, 1242}

and sends (3861,1242) to Alice. Alice multiplies what she receives by $N_A$ and Bob multiplies what he receives by $N_B$:

In[20]:= multell[{3861, 1242}, 12, 1, 7206, 7211]

Out[20]= {1472, 2098}

In[21]:= multell[{1794, 6375}, 23, 1, 7206, 7211]

Out[21]= {1472, 2098}

Therefore, Alice and Bob have produced the same key.