Elliptic Curves over local rings $F_q[x]/x^k$

In this repository you can find scripts and computations for our paper Multiplication polynomials for elliptic curves over finite local rings (also available on arxiv). For a quick introduction to the code look at quickstart.magma. A more detailed description of the repository can be find below.
Should you have any question or suggestion, do not hesitate to contact the authors:

• Daniele Taufer: name.surname@gmail.com
• Riccardo Invernizzi: name.surname@kuleuven.be

Sections:

• Paper Computations: the scripts used in the paper, along with their results, are briefly presented;
• Useful Scripts: code to easily work with elliptic curve over these rings.

Paper Computations

• short_sum_verification.magma: verification of the equality between the second addition law in Bosma - Lenstra, 1995 (except for a minor typo) and our short form;
• zfx_fast.py and zfxred_fast.py: python script to compute the symbolic expression of $z$ coordinates of points as a polynomial in their $x$ coordinate over $\mathcal{O}$ (in extended and reduced Weierstrass form respectively). The parameter $k$ can be set before running the script. The output is saved as a loadable magma script called zfx_stored_{k}.magma (extended form) or zfxred_stored_{k}.magma. Two examples can be found in zfx_stored_30.magma and zfxred_stored_300.magma;
• inspection.magma: inspection of addition laws modulo the ideal generated by $P_x^2, P_z$;
• ind.magma / indred.magma: computation of the $\psi_i$ polynomials as described in the paper; the output is stored as loadable magma script in psi_stored.magma (resp. psired_stored.magma). An example on how to load these polynomials can be found in psi_loaded_30.magma and psired_loaded_222.magma;
• except_coeff.magma: comparison between the occurrence of the main case and the exceptional ones for non-anomalous curves and small $p$;
• ex1.magma / ex2.magma: examples of behaviour of the minimum degree of points in the exceptional cases;
• proof_23.magma: verification of conditions (C1), (C2) and (C3) for $p=2,3$;
• proof_short.magma: verification of conditions (C1), (C2) and (C3) for $5 \leq p \leq 13$, using short weierstrass form; conditions (C2) and (C3) are tested as far as possible also for $p \leq 100$;
• d_log.magma: algorithm to break the discrete logarithm over $E^\infty$.

Useful scripts

• utils.magma: the file containing most of the useful function to work with elliptic curves over $F_q[x]/x^k$, including point addition and multiplication, lifting and others;
• quickstart.magma: a showcase of usage of the most important functions of utils.magma;
• grp.magma: samples random points from random curves with fixed parameters, and computes their order and $p$-multiples; useful to infer the group structure, or at least the highest order of points in the group (since point with highest order appears more often); parameter choices are explained in the script;
• zfx_stored_30.magma / zfxred_stored_300.magma: stored values of the $z$ coordinate of a point over $\mathcal{O}$ as a polynomial function of its $x$ in the extended (resp. reduced) form, for $k=30$ (resp. $k=300$). Notice that a symbolic polynomial ring must be defined before loading; specific loading instructions are provided in each file;
• psi_stored_30.magma: stored values of $\psi_i$ for $i \leq 30$ in the extended form; the loader script psi_loaded_30.magma can be used to import them, otherwise a symbolic polynomial ring must be defined before loading; smaller sets are provided for faster loading, at psi_stored_27.magma and psi_stored_17.magma (each one with its own loader);
• psired_stored_222.magma: same script for short form; loader at psired_loaded_222.magma, smaller version at psired_stored_129.magma;