We want to graph the elliptic curve $y^2=x(x-1)(x+1)$.

First, we create a string $v$ that contains the equation we wish to graph.

>> v=’y^2 - x*(x-1)*(x+1)’;

Next we use the ezplot command to plot the elliptic curve.

>> ezplot(v,[-1,3,-5,5])

The plot appears in Figure C.1. The use of $[-1\text{,}3\text{,}-5\text{,}5]$ in the preceding command is to define the limits of the $x$-axis and $y$-axis in the plot.

Figure C.1 Graph of the Elliptic Curve $y^2=x(x-1)(x+1)$.

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

>> addell([1,3],[3,5],24,13,29)

ans =
    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)$. (Note: addell([x,y],[u,v],b,c,n) is only programmed to work for odd $n$.)

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

>> addell([1,3],[inf,inf],24,13,29)

ans =
    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$.

>> multell([1,3],7,24,13,29)

ans =
    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.

>> multsell([1,3],40,24,13,29)

ans =
   1:    1     3
   2:    11    10
   3:    23    28
   4:    0     10
   5:    19    9
   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:   inf   Inf
  20:    1     3
  21:    10    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:   inf   inf
  39:    1     3
  40:    10    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)$:

>> multell([1,3],12,-5,13,11*19)

Elliptic Curve addition produced a factor of n, factor= 19
Multell found a factor of n and exited

ans =
   []

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

>> multsell([1,3],12,-5,13,11*19)

Elliptic Curve addition produced a factor of n, factor= 19
Multsell ended early since it found a factor

ans =
1:   1     3
2:   91    27
3:   118   133
4:   148   182
5:   20    35

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:

>> multsell([1,3],20,-5,13,19)

ans =
 1:    1     3
 2:   15     8
 3:    4     0
 4:   15    11
 5:    1    16
 6:   Inf   Inf
 7:    1     3
 8:   15     8
 9:    4     0
10:   15    11
11:   15     8
12:   Inf   Inf
13:    1     3
14:   15     8
15:    4     0
16:   15    11
17:    1    16
18:   Inf   Inf
19:    1     3
20:   15     8

>> multsell([1,3],20,-5,13,11)

ans =
 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:   Inf   Inf
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$.

>> multell([2,4],factorial(12),-10,28,193279)

Elliptic Curve addition produced a factor of n, factor= 347
Multell found a factor of n and exited

ans =
   []

>> multell([1,1],factorial(12),11,-11,193279)

ans =
    13862    35249

» multell([1,2],factorial(12),17,-14,193279)

Elliptic Curve addition produced a factor of n, factor= 557
Multell found a factor of n and exited

ans =
   []

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 $272=2\cdot 7\cdot 9$, 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 an intermediate step in the calculation, the program required adding the points $(184993\text{,}13462)$ and $(20678\text{,}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$:

>> multell([4,11],3,3,45,8831)

ans =
    413    1808

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

>> multell([4,11],8,3,45,8831)

ans =
    5415    6321

>> addell([5,1743],multell([413,1808],8,3,45,8831),3,45,8831)

ans =
    6626    3576

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

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:

>> addell([6626,3576],[673,-146],3,45,8831)

ans =
   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

>> multell([3,5],12,1,7206,7211)

ans =
    1794    6375

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

>> multell([3,5],23,1,7206,7211)

ans =
    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$:

>> multell([3861,1242],12,1,7206,7211)

ans =
    1472    2098

>> multell([1794,6375],23,1,7206,7211)

ans =
    1472    2098

Therefore, Alice and Bob have produced the same key.