Modulo Errors

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).