D.10 Computations for Chapter 21

Elliptic curves

Let’s set up the elliptic curve y2x3+2x+3 mod 7:

E=EllipticCurve(IntegerModRing(7),[2,3])

The entry [2,3] gives the coefficients a, b of the polynomial x3+ax+b. More generally, we could use the vector [a,b,c,d,e] to specify the coefficients of the general form y2+axy+cyx3+bx2+dx+e. We could also use GF(7) instead of IntegerModRing(7) to specify that we are working mod 7. We could replace the 7 in IntegerModRing(7) with a composite modulus, but this will sometimes result in error messages when adding points (this is the basis of the elliptic curve factorization method).

We can list the points on E:

E.points()
[(0:1:0), (2:1:1), (2:6:1), (3:1:1), (3:6:1), (6:0:1)]

These are given in projective form. The point (0:1:0) is the point at infinity. The point (2:6:1) can also be written as [2, 6]. We can add points:

E([2,1])+E([3,6]) 
(6 :  0 :  1)

E([0,1,0])+E([2,6]) 
(2 :  6 :  1)

In the second addition, we are adding the point at infinity to the point (2, 6) and obtaining (2, 6). This is an example of +P=P. We can multiply a point by an integer:

5*E([2,1]) 
(2 :  6 : 1)

We can list the multiples of a point in a range:

for i in range(10): 
   print(i,i*E([2,6])) 
 
(0, (0 : 1 : 0)) 
(1, (2 : 6 : 1)) 
(2, (3 : 1 : 1)) 
(3, (6 : 0 : 1)) 
(4, (3 : 6 : 1)) 
(5, (2 : 1 : 1)) 
(6, (0 : 1 : 0)) 
(7, (2 : 6 : 1)) 
(8, (3 : 1 : 1)) 
(9, (6 : 0 : 1))

The indentation of the print line is necessary since it indicates that this is iterated by the for command. To count the number of points on E:

E.cardinality() 
6

Sage has a very fast point counting algorithm (due to Atkins, Elkies, and Schoof; it is much more sophisticated than listing the points, which would be infeasible). For example,

p=next_prime(10^50) 
E1=EllipticCurve(IntegerModRing(p),[2,3]) 
n=E1.cardinality() 
p, n, n-(p+1) 
(100000000000000000000000000000000000000000000000151, 
99999999999999999999999999112314733133761086232032, 
-887685266866238913768120)

As you can see, the number of points on this curve (the second output line) is close to p+1. In fact, as predicted by Hasse’s theorem, the difference n(p+1) (on the last output line) is less in absolute value than 2p2×1025.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset