Skip to content

Latest commit

 

History

History

complex_multiplication

readme.md

Complex Mulitiplication

Overview

This module provides functionality to construct elliptic curves via the Complex Multiplication (CM) method. The implementation follows the procedure described in [[W08]](/references/Washington 2008 --- Elliptic Curves Number Theory and Cryptography.pdf). This module contains three files:

  • complex_multiplication.py, which contains the algorithm for the CM method;

  • complex_multiplication_examples.py, which contains code examples;

  • complex_multiplication_tests.py, which contains unit tests.

Throughout, q denotes the prime size of the base field; t denotes the trace of Frobenius; r denotes the prime size of the group; k denotes the embedding degree; D denotes the (negative) fundamental discriminant.

Methods

Here is an overview of the methods in complex_multiplication.py:

make_curve(q, t, r, k, D, debug=False)

Runs the CM method and returns an elliptic curve E(Fq) that has trace t, a subgroup of order r with embedding degree k, and fundamental discriminant D. Setting debug=True will output a print statement when the Hilbert class polynomial is computed, since this computation is the bottleneck of the algorithm.

small_A_twist(E)

Returns a curve E' that is isogenous to E and has small coefficient A in the curve equation y2 = x3 + Ax + B.

small_B_twist(E)

Returns a curve E' that is isogenous to E and has small coefficient B in the curve equation y2 = x3 + Ax + B.

test_curve(q, t, r, k, D, E)

Tests that E(Fq) has trace t, a subgroup of order r with embedding degree k, and fundamental discriminant D.

Examples

The code examples in complex_multiplication_examples.py show how to run the CM method to construct an elliptic curve.

Tests

The test in complex_multiplication_.py runs the CM method many times on random test cases. The test also checks the two edge cases when the j-invariant equals 0 and 1728.