ecfactory: A SageMath Library for Constructing Elliptic Curves

Overview

The ecfactory library is developed by the SCIPR Lab project and contributors (see AUTHORS file) and is released under the MIT License (see LICENSE file). The library implements algorithms to construct elliptic curves with certain desired properties; specifically, it provides the following functionality.

1. Complex Multiplication method
2. Cocks-Pinch method
3. Dupont-Enge-Morain method
4. Solver for Pell equations
5. Miyaji-Nakabayashi-Takano curves
6. Barreto-Naehrig curves
7. Elliptic-curve chains (via the Cocks-Pinch method)
8. Elliptic-curve cycles (via MNT curves)

Each of the above is packaged as a Python module in a corresponding subfolder under the ecfactory folder.

Throughout, a curve E is specified as a tuple (q,t,r,k,D) where: q is the prime size of the base field; t is the trace of Frobenius; r is the prime size of the subgroup (which can be the size of the entire group); k is the embedding degree; and D is the (negative) fundamental discriminant. From the tuple (q,t,r,k,D), the curve equation can be found using the Complex Multiplication method.

Requirements

The library requires a working SageMath installation, and has been tested on SageMath version 6.8, 7.2 and 9.7.

Installation

To install, use sage pip:

$ git clone https://github.com/scipr-lab/ecfactory.git && cd ecfactory && sage -pip install .

To import and use the library, write

import ecfactory

Methods can now be invoked as

ecfactory.module_name.method_name

For example,

ecfactory.dupont_enge_morain.run(50,5)

To import only one module, write

import ecfactory.module_name as other_name

Methods can now be invoked more concisely as

other_name.method_name

For example,

import ecfactory.dupont_enge_morain as dem
dem.run(50,5)

Tutorials

Each subfolder contains a readme, code examples, and unit tests. The methods are described in the readme, and the code examples show how to run the relevant methods. Many of the algorithms and tests are probabilistic, and the random seed can be set using set_random_seed(s).

Additionally, the utils module contains global functions that filter the curves found by all algorithms. See the utils folder for more details.