Echidna Algorithms
Algorithms for Elliptic Curves and Higher Dimensional Analogues


Echidna Algorithms Latest version: echidna-5.0.spkg Previous versions: echidna-4.0.spkg

This is the complete Sage package for Echidna Algorithms, version 5.0 (for Magma V2.19 or higher). This code is designed for computational and algorithmic research in the arithmetic of curves, Jacobian, number fields (particularly CM fields), lattices, and algebras, over a period of many years, including code contributions by and/or the output of collaborations with Robert Carls, Pierrick Gaudry, Martine Girard, David Gruenewald, Thomas Houtmann, Hamish Ivey-Law, Jürgen Klüners, David Lubicz, Christophe Ritzenthaler, Benjamin Smith, William Stein, Helena Verrill, Annegret Weng, Geordie Williamson, and others. Description of individual packages and some documentation can be found below.

This package is a bzip2'ed tar file of open source Magma code. For databases of modular polynomials, defining modular curves and their correspondences, class polynomials for genus 1 and 2, quaternion algebras, and of Brandt modules and their decompositions and Hecke algebra structures, consult the page Echidna Databases for associated data.

For Magma code development, emacs users may find this customizable magma mode may be of use (version is adapted from an initial version of William Stein, which was in turn derived from the GNU elisp shell.el).

INSTALLATION: The tar file expands (tar -xvjf echidna-5.0.spkg) into a directory structure echidna-5.0/[src,dbs]. To avoid the need to modify the path in echidna-5.0/src/System/directory.m, you should define an ECHIDNA_ROOT environment variable. For instance in bash, place:

export ECHIDNA_ROOT=$HOME/echidna-5.0

in your .bash_profile. Now, to automatically load Echidna on startup, place the following line in your .magmarc file:

AttachSpec(GetEnv("ECHIDNA_ROOT")*"/src/echidna.spec");

or call this from Magma.

BUG REPORTS: Please report any bugs to David Kohel David.Kohel@univ-amu.fr.


Package Title Documentation
Quaternion Algebras AlgQuat.pdf
This is a package for quaternion algebras and their orders, with special functionality for quaternion algebras over the rationals.
Brandt Modules ModBrdt.pdf
This is a package for working in the free module generated by the left ideal classes of a definite quaternion algebra over the rationals.
AGM-X0(N) AGM-X0.pdf
This is a package for point counting in elliptic curves over finite fields of characteristics 2, 3, 5, 7, and 13. In a generalization of the p-adic lifting method of Mestre, this algorithms uses models for modular curves of genus zero to lift CM points p-adically to characteristic zero, and "read off" the trace of Frobenius from its action on the space of differentials of a parametrized curve. This package complements my Asiacrypt'03 article "The AGM-X0(N) Heegner point lifting algorithm and elliptic curve point counting".
Picard Groups PicCrv.pdf
This is a package for working in the Picard group of a curve. The present implementation forms the Picard group of the nonsingular resolution of the input curve.
Singular Cubic Curves
This package is an implementation of the group law on possibly singular cubic curves, extending the elliptic curve group law to this larger class of curves.
Singular Hyperelliptics
This package implements the generalized Jacobian of a singular hyperelliptic curve as described in my preprint "Constructive and destructive aspects of torus-based cryptography". The file jachypsng.m is sample code demonstrating its use for jacobian arithmetic, discrete logarithms, and morphisms between jacobians and the multiplicative group as described in the preprint. The package for singular cubic curves is also used in this file.
Genus 2 Curve Invariants and Canonical Lifts
This package is a bundle of code for computing with moduli of genus 2 curves, Igusa invariants, Rosenhain invariants, and theta null values and their canonical lifts. The underlying algorithms represents research with Ritzenthaler, and subsequently Gaudry, Houtman, and Weng; with Ben Smith; and with Carls and Lubicz.
Jacobians of Genus 2 Curves
This package contains code for computing a projective embedding for the Jacobian of a genus 2 curve, and its formal group. This includes code written with Geordie Williamson.
Hyperelliptic Jacobians
Various algorithms for computing endomorphism rings of a hyperelliptic Jacobians and simple index calculus relation calculations.
Quartic CM Fields
Algorithms for quartic CM fields (invariants, reflex fields, real subfields, etc.).
Genus 3 Curve Invariants
This computes the Dixmier-Ohno invariants of a plane quartic (given as a homogeneous polynomial in three variables) and the Shioda invariants of a genus 3 hyperelliptic (see Shioda, On the graded ring of invariants of binary octavics).
Cryptosystems
This is a teaching package for use in a course in classical cryptography, covering substitution and transposition ciphers, linear feedback shift registers, RSA, and ElGamal. See my former MATH3024, which contains information on its use (particularly the tutorials), but see the course page for my ICE-EM/AMSI Summer School course in Cryptography for my book and an expanded cryptography package in SAGE.
User Databases DBUser.txt
This package provides an interface to the various databases on the Echidna Databases page.

This page hosts links to code and documentation in areas related to research in number theory and arithmetic geometry developed in association with research in this area, and made available under the GNU Public License version 2 or higher (see GPL) and the GNU Free Documentation License (see FDL), respectively. They are made available in the spirit of open academic exchange of ideas and advancing research. To use code developed in Magma you will need a copy of Magma. The algorithms represented here build on thesis work at The University of California, Berkeley, and subsequent postdoctoral research at the National University of Singapore, the Mathematical Sciences Research Institute (Berkeley), the University of Sydney, and the Institut de Mathématiques de Marseille, with contributions and inspiration from many collaborators (see above).
David Kohel (David.Kohel@univ-amu.fr) Institut de Mathématiques de Marseille
Valid HTML 4.0!