Modulo Errors

I’ve added a couple of extra toys to my Maple procedures for elliptic curves. The major change is that it now supports calculation over some finite fields; that is, the integers modulo some prime. To activate this, set workModM to true and specify a modulus M. Then the usual commands ella, ellm, ncopies and mnadd will compute answers mod M instead.

This also makes it much more likely that you’ll be interested in the order of a point, so a procedure modgetorder is included to calculate this by brute force- that is, repeated addition until the zero element is reached.

This makes questions of the type I faced in MA40188: Algebraic Curves much easier. For instance, consider the curve

Over the field with 37 elements, and with a suitable dehomogenisation, the point P: (x,y)=(0,23) is easily verified as an element of E. Then we may easily determine the point Q=-2P, the third intersection of E with the tangent to E at P:

>read “gla.mpl”;

> a_1:=0;a_2:=0;a_4:=-9;a_3:=0;a_6:=11;

>workModM:=true;

>

>M:=37;

>Q:=ncopies(-2,0,23);

1,22

So Q=(1,22). Further, Q is an inflexion point: that is, the tangent to E at Q meets E three times at Q. In terms of the group law, this means -2Q=Q, or equivalently 3Q=0. We can verify this in a couple of ways:

> ncopies(3,Q);

zero

> modgetorder(Q);

3

Since Q=-2P and 3Q=0, it should follow that 6P=0. Which, fortunately, it does:

> modgetorder(0,23);

6

Here are some applications of the procedures developed in the previous post.

Example 1

We consider example 2.4/problem 3.4 from Silverman;

By inspection we can identify some integer points, such as P₁=(-2,3) and P₃=(2,5). A brute force search for x in the range -1000 to 1000 generates the following results-

> #naive point search;

> for k from -1000 to 1000 do

> if(type(simplify((k^3+17)^(1/2)),integer)) then print(k,simplify((k^3+17)^(1/2))); end;

> end;

-2, 3

-1, 4

2, 5

4, 9

8, 23

43, 282

52, 375

Silverman tells us there is a further point, P₈=(5234,378661), plus we have missed all the inverses of our points (since only the positive square root was computed). Brute force on the range -6000 to 6000 of course uncovers P₈, but this computation takes 70.6 seconds, 10.24mb of memory and produces alarming sounds from my new office computer. Silverman observes that (due to a result of Nagell) the rational points are generated by integer combinations of P₁, P₃, so we can proceed by testing some of these instead:

> read “gla.mpl”;

> a_1:=0;a_3:=0;a_2:=0;a_4:=0;a_6:=17; #setting
up the curve;

>#smarter search

> for i from -5 to 5 do

> for j from -5 to 5 do

> if(type(mnadd(i,j,-2,3,-1,4)[1],integer) and type(mnadd(i,j,-2,3,-1,4)[2],integer)) then print(i,j,mnadd(i,j,-2,3,-1,4));

> end if;

> end:

> end:

-3, -2, 43, -282

-2, -3, 5234, -378661

-2, -1, 2, -5

-2, 0, 8, 23

-1, -1, 4, 9

-1, 0, -2, -3

-1, 1, 52, -375

0, -1, -1, -4

0, 1, -1, 4

1, -1, 52, 375

1, 0, -2, 3

1, 1, 4, -9

2, 0, 8, -23

2, 1, 2, 5

2, 3, 5234, 378661

3, 2, 43, 282

All sixteen points are recovered in 0.02 seconds, consuming merely 0.31mb of memory!

Of course, for this example I’m cheating somewhat because I know where I’d like to get to in that I know this list is complete; although a priori there’s no indication of how large the arguments m,n needed to be to generate points such as P₇ or P₈. Nonetheless, this indicates that the procedures allow for more rapid exploration of points on the curve, even if they don’t prove anything (besides existence) by themselves.

Example 2

Maple’s own algcurves package can also be useful to tackle problems given in projective terms. For instance, we can rapidly demonstrate the first result claimed in Exercise 3.3b. Here we are concerned with the curve

which homogenizing away from Z=0 gives

However, this is not of Weierstrass form; but we can retrieve this from Maple:

> with(algcurves):

> f:=x^3+y^3-A

> Weierstrassform(f,x,y,x0,y0)

This yields

But this is not quite of the Weierstrass form as used in Silverman; we substitute -x₀ for x₀ to arrive at

That is, we have that the curve coefficients a_i are all zero except a₆=27A²/4; we also have an isomorphism φ between E and its Weierstrass form given coordinatewise. We can verify with the procedure j_invariant that these are indeed the same curve (it turns out to have j invariant zero, too). Moreover, we can show the desired result, that

For this, let P=(x_0,y_0) a point on the curve in Weierstrass form. Then we compute -P:

> a_1:=0;a_3:=0;a_2:=0;a_4:=0,a_6=-27*A^2/4:

> read “gla.mpl”:

> ellm(x_0,y_0);

x_0, -y_0

Then, identifying P with a projective point via the isomorphism, we find

Which is the desired result.

Update: These procedures have been replaced with a more general (and efficient) set: see this post!

Overview

These maple procedures implement the group law algorithm for an elliptic curve as given in Chapter III Section 2.3 of Silverman’s The Arithmetic of Elliptic Curves. In particular, they can handle the group identity symbolically as it arises during calculations.

Loading the procedures

The procedures can be downloaded as the maple file gla.mpl, which should be placed in whatever directory Maple expects to find it. To be more helfpul, this is probably your home directory on Unix based systems; on Windows it could be the application directory, although if you invoke maple by opening a worksheet, it’ll be the directory that sheet resides in. If you’re unsure, entering the following:

> x:=5;

> save x, “test.m”;

Will create a file test.m which you can then search for to determine the appropriate directory.

Having established where the file goes, you then need to read it into Maple:

> read “gla.mpl”;

Which after some shameless self-promotion gives you the procedures. The assumption is that you have an Elliptic curve given by a Weierstrass equation determined by coefficients a₁,…,a₆ as in Silverman:

You can of course work in full generality without defining these coefficients. The point at infinity is referred to as zero, whilst a point P=(x,y) can be specified as x,y (using (x,y) will likely give errors).

The procedures

Looking at the source you’ll find various procedures, some of which are only needed for the internal workings- in particular, elladd cannot handle zero and should not be used directly. The operations available are:

Elliptic addition (ella)

Addition with the group law is achieved by a call to the ella procedure; a typical call is ella(x1,y1,x2,y2) to compute x1,y1+x2,y2=P₁⊕P₂; however, you may substitute zero for either or both points (for instance, ella(zero,x,y) is valid). In accordance with 2.3(b) this either returns zero or x(P₁+P₂),y(P₁+P₂).

Inverse of a point (ellm)

Given a point P=(x,y), ellm(x,y) returns the group inverse, i.e., the point -P. zero is understood and is its own inverse.

Integer multiples (ncopies)

Repeated iteration of ella for a single point P=(x,y) is made available by ncopies(n,x,y), for n an integer. As before, zero may be (somewhat pointlessly) subsituted for x,y. Care is taken to ensure zero is appropriately handled at each stage, and thus may be returned as an answer (always, for n=0). Negative values of n are of course handled by returning n copies of -P, so this provides an alternative to ellm.

Addition of integer multiples (mnadd)

For convenience, two such integer multiples [m]P₁,[n]P₂ can be added using mnadd(m,n,x1,y1,y2); as usual zero can replace a pair of coordinates (or both).