Html Documentation CM 0.3

This manual documents how to install and use CM, version 0.3


Next: , Previous: , Up: Top   [Index]

1 Introduction

The CM software implements the construction of ring class fields of imaginary quadratic number fields and of elliptic curves with complex multiplication via floating point approximations. It consists of libraries that can be called from within a C program and of executable command line applications. For the implemented algorithms, see En09a.

Given an imaginary quadratic discriminant D<0, the associated ring class field is generated by the values of modular functions in special arguments taken from the quadratic field Q(sqrt D); these values are called singular values or class invariants. Depending on D, different modular functions need to be chosen; we call the suitable ones class functions. CM implements (to a greater or lesser extent) all major class invariants described in the literature.

Licence

CM is free software; you can redistribute it and/or modify it under the terms of the GNU General Public licence as published by the Free Software Foundation; either version 3 of the licence, or (at your option) any later version.

CM is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public licence for more details.

You should have received a copy of the GNU General Public licence along with CM; see the file COPYING. If not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.


Next: , Previous: , Up: Top   [Index]

2 Installation


Next: , Up: Installation   [Index]

2.1 Instructions

CM relies on a number of external libraries, which need to be installed before compiling CM: GNU MP (see Gr09, version 4.3.2 or higher), GNU MPFR (see HaLePeZi09, version 3.0.0 or higher), MPC (see EnThZi09, version 1.0.0 or higher), MPFRCX (see En09b, version 0.4 or higher) and PARI (see Pa10, version 2.7.0 or higher, compiled with GMP as the arithmetic kernel). Compilation of CM needs a standards compliant C compiler (preferably GCC).

These are the steps needed to install CM, provided that the required libraries are installed in standard locations:

  1. tar xzf cm-0.3.tar.gz
  2. cd cm-0.3
  3. ./configure
  4. make

    This compiles CM.

  5. make check

    This performs a few tests to check that CM has been built correctly.

    If you get error messages, please report them to the mailing list (cf. Mailing list).

  6. make install

    This copies the executable applications into the directory /usr/local/bin, the header files into /usr/local/include, the library files into /usr/local/lib, the data files into subdirectories of /usr/local/share/cm (see Data) and the file cm.info into /usr/local/share/info.

    It is possible to pass the option ‘--prefix=/my/install/directory’ to the ‘./configure’ step above, so that all files go into subdirectories of /my/install/directory instead of /usr/local.

If auxiliary libraries are to be found in non-standard locations, these need to be passed in the ‘./configure’ step above by adding parameters

For an exhaustive list of configuration parameters, execute ‘./configure --help’.


Next: , Previous: , Up: Installation   [Index]

2.2 Documentation

Besides the texinfo documentation obtained by a simple invocation of ‘make’, the commands ‘make dvi’, ‘make ps’, ‘make pdf’ and ‘make html’ create the documentation in the corresponding formats.


Next: , Previous: , Up: Installation   [Index]

2.3 Data

Some parameterised families of class functions need additional data (namely, modular polynomials), which depend on the parameter value, to deduce the equation of an elliptic curve from the class polynomial. A few modular polynomials for double eta quotients are provided and stored in /usr/local/share/cm/df (or the subdirectory share/cm/df of the installation directory provided with the ‘--prefix’ configuration option, respectively); those for Atkin functions can be found in /usr/local/share/cm/af, and so on.

An infinite amount of data is needed to handle all possible discriminants with a given family of class functions, and already covering all moderately sized discriminants would require gigabytes of data. So only a very small sample of modular polynomials is currently distributed; if you need more, please write to the mailing list (cf. Mailing list).


Previous: , Up: Installation   [Index]

2.4 Mailing list

Bug reports should go to the mailing list cme-discuss@lists.gforge.inria.fr, which, as its name indicates, may also be used for discussions around the software.


Next: , Previous: , Up: Top   [Index]

3 Applications

At the time being, CM comes with two sample applications, ‘cm’ and ‘classpol’. Both take the same command line arguments. Being given a negative discriminant D, passed to the program through the parameter ‘-d’ directly followed (without separating space) by the absolute value |D| of the discriminant, ‘cm’ computes and outputs a cryptographically suitable elliptic curve with complex multiplication by D. The program chooses a 200 bit prime p and computes a curve E : Y^2 = X^3 + a*X + b over Fp of “almost prime” cardinality, that is, a cardinality that is either itself prime or twice or four times a prime depending on D (prime cardinalities may only be reached for D = 5 (mod 8)). On the other hand, ‘classpol’ computes and outputs only the class polynomial without an associated elliptic curve.

In normal operation, the programs output only the result of their computations. For more details and progress reports, use the command line parameter ‘-v’.

By default, both programs use the j-function as class function, which works for arbitrary discriminants, but is a poor choice for efficiency reasons since it generates very large class polynomials. It is recommended to specify alternative class invariants, which, for |D| tending to infinity, allow to gain a constant factor in the size of the computed objects. A class invariant is selected by the parameter ‘-i’, directly followed (without space) by a word characterising a class function or a parameterised family of such functions; in the latter case, an optimal parameter value is computed by the program. The following class functions are implemented:

Example invocations

If you experience difficulties creating your own application using the libraries described in Libraries, or are missing functionalities, please do not hesitate to use the mailing list, cf. Mailing list.


Next: , Previous: , Up: Top   [Index]

4 Libraries

The code of CM is organised in libraries to make the different functions accessible to external applications. With a few exceptions, the names of all publicly accessible, non-static functions and types start by cm_ to create a name space proper to CM.


Next: , Up: Libraries   [Index]

4.1 cm_class

The library cm_class contains the main code needed for computing class polynomials and elliptic curves with prescribed complex multiplication. For the time being, only the interface needed to implement the applications of Applications, is made public in cm_class.h. Further internal functions, such as the computation of the algebraic conjugates of a class invariant, can be found in cm_class-impl.h and may be made public in the future.

Type: int_cl_t

This signed 64 bit integer type is used for discriminants.

Type: cm_class_t

This structural type holds information related to a class polynomial, from the discriminant and class function set at initialisation to computed data such as class numbers and the class polynomial.

Function: void cm_class_init (cm_class_t *c, int_cl_t d, char inv, bool verbose)

Sets the discriminant of c to disc and the class function to inv. The variable inv may take one of the predefined constants CM_INVARIANT_J, CM_INVARIANT_DOUBLEETA, CM_INVARIANT_GAMMA3, CM_INVARIANT_GAMMA2, CM_INVARIANT_WEBER, CM_INVARIANT_SIMPLEETA, CM_INVARIANT_MULTIETA or CM_INVARIANT_ATKIN, corresponding to the class functions enumerated in Applications. For a parameterised family of class functions, a suitable parameter value is computed if it exists; otherwise, the program execution is aborted. Moreover, the class number is computed and space is allocated accordingly for the class polynomial.

If verbose is set to true, some information is printed on screen during execution.

Function: void cm_class_compute_minpoly (cm_class_t c, bool checkpoints, bool write, bool print, bool verbose)

Takes a previously initialised cm_class_t object c and computes the corresponding class polynomial. If print is true, the polynomial is printed on screen, if write is true, it is written to disc into the subdirectory cp.

The variable checkpoints is only relevant for record computations; if set to true, intermediate results are written to disk and read in again if the program execution is interrupted and resumed later.

If verbose is set to true, some information is printed on screen during execution.

Function: void cm_class_clear (cm_class_t *c)

This is the counterpart to cm_class_init and should be called once the class polynomial is not needed any more to free the allocated space.

Function: void cm_curve_compute_curve (int_cl_t d, char inv, int fieldsize, const char* modpoldir, bool readwrite, bool print, bool verbose)

Computes a cryptographically suitable curve with complex multiplication by d over some prime field of fieldsize bits, using the class function designated by inv.

If readwrite is set to true, the function tries to read the class polynomial from a file; if the file is not present, the class polynomial is computed and written to a file.

If print is set to true, the j-invariant and coefficients a and b of the curve are printed on screen, if verbose is set to true, additional progress information is printed.

The variable modpoldir holds the base directory of the modular polynomials needed to derive elliptic curves from roots of class polynomials; the modular polynomials themelves are stored in subdirectories df, af and so on of the base directory. In the standard installation, this is /usr/local/share/cm.


Next: , Previous: , Up: Libraries   [Index]

4.2 cm_common

This library is split off from cm_class and contains functions that can be seen as internal to the class polynomial computation, but that can also be useful in a broader context (notably, the computation of modular polynomials).


Previous: , Up: Libraries   [Index]

4.3 mpfpx

This library is used for low degree polynomials over prime fields, the characteristic of which is stored in a global variable. It is in a very rudimentary state.


Next: , Previous: , Up: Top   [Index]

References


Previous: , Up: Top   [Index]

Index

Jump to:   A   B   C   D   H   I   L   M   S  
Index Entry  Section

A
applications: Applications

B
bug reporting: Mailing list

C
class function: Introduction
class invariant: Introduction
cm_class: cm_class
cm_class_clear: cm_class
cm_class_compute_minpoly: cm_class
cm_class_init: cm_class
cm_class_t: cm_class
cm_common: cm_common
cm_curve_compute_curve: cm_class
copying conditions: Introduction

D
data: Data
documentation: Installation
documentation: Documentation

H
height factor: Applications
help: Mailing list

I
installation: Installation
installation: Instructions
introduction: Introduction
int_cl_t: cm_class

L
libraries: Libraries
licence: Introduction

M
mailing list: Mailing list
modular polynomial: Data
mpfpx: mpfpx

S
singular value: Introduction
singular value: Introduction

Jump to:   A   B   C   D   H   I   L   M   S