We want to graph the elliptic curve .
First, we create a string 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 in the preceding command is to define the limits of the -axis and -axis in the plot.
Add the points (1,3) and (3,5) on the elliptic curve .
>> addell([1,3],[3,5],24,13,29)
ans =
26 1
You can check that the point (26,1) is on the curve: . (Note: addell([x,y],[u,v],b,c,n)
is only programmed to work for odd .)
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 returns the point .
Let be a point on the elliptic curve . Find .
>> multell([1,3],7,24,13,29)
ans =
15 6
Find for 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 , where is on the elliptic curve :
>> 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 , 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 , 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 and the elliptic curve
For to lie on the curve, we take . We’ll also take
Now we compute multiples of the point . We do the analog of the method, so we choose a bound , say , and compute .
>> 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, ends up at infinity mod 557 and is infinity mod 347. Since , it has a prime factor larger than , so is not infinity mod 557. But divides , so is infinity mod 347.
On the second curve, mod 347, and mod 557. Since and , we don’t expect to find the factorization with this curve.
The third curve is a surprise. We have mod 347 and mod 557. Since is prime and , we don’t expect to find the factorization with this curve. However, by chance, an intermediate step in the calculation of yielded the factorization. Here’s what happened. At an intermediate step in the calculation, the program required adding the points and . 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 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 and the point is . Alice’s message is the point .
Bob has chosen his secret random number and has computed :
>> multell([4,11],3,3,45,8831)
ans =
413 1808
Bob publishes this point. Alice chooses the random number and computes and :
>> 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 :
>> multell([5415,6321],3,3,45,8831)
ans =
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:
>> 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 and the point is . Alice chooses her secret and Bob chooses his secret . 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 and Bob multiplies what he receives by :
>> 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.