**Context.**
During ECC 2011, a
summer school will be
organised on Elliptic and Hyperelliptic Curve Cryptography.
Besides classical lectures, there will be some Coding sprints based on the
Sage software.
This page gives some ideas of possible topics for those coding sprints.
Comments and suggestions are welcome.

**Important note.** To ensure that all what will be done during those
coding sprints is not lost, participants are requested to submit their
work (source code, suggestions, bug reports, benchmarks, pointers to
algorithms, ...) to the Sage
trac server (first ask for an account as indicated in the beginning of
that page).

To contribute a patch for Sage, please follow the page from Sébastien Labbé. In short:

1) first type `sage -clone trac11548`, assuming you want to work on
ticket 11548 for example. This will avoid polluting your main copy of Sage.
You can come back to the "main" copy with `sage -b main`, and to
ticket trac11548 with `sage -b trac11548`.

2) assume you want to patch the file `ell_point.py`.
First locate it in the `trac11548` branch.
It should be something like
`/usr/local/sage/devel/sage-trac11548/sage/schemes/elliptic_curves/ell_point.py`

3) then modify this file with your favorite text editor

4) run `sage -br` to rebuild Sage with the modified file, and check
your patch is ok.

5) once your patch is fine, from within Sage, type `hg_sage.commit()`,
and after typing `q`
enter a commit log line giving the ticket number (11548) and saying
what you have done

6) then type `hg_sage.export('tip')` and exit Sage

7) a file `nnnnn.patch` was created in the current directory, then
rename that file to `trac11548.patch` and upload it on the page
corresponding to ticket 11548 on the Sage trac server.

- Luca de Feo proposes to improve elliptic curve morphisms
- Jean-Pierre Flori proposes a basic version of point counting for elliptic curve using canonical lift. See also ticket 11548.
- Luca de Feo proposes to cythonize
`EllipticCurvePoint_finite_field`(here on`tarte.loria.fr`with Sage 4.7):

`sage: K = GF(next_prime(2^256))`

sage: a = K.random_element()

sage: b = K.random_element()

sage: timeit('a*b')

625 loops, best of 3: 549 ns per loop

sage: E = EllipticCurve([a,b])

sage: P = E.random_point()

sage: timeit('(2^256-1)*P')

25 loops, best of 3: 23.7 ms per loop

Magma 2.17-7 is 1.5 times faster for the first multiply (355ns instead of 549ns), but about 14 times faster in the second multiply (1.7ms instead of 23.7ms):`> K := GF(NextPrime(2^256));`Challenge: beat Magma on that example!

> a := Random(K);

> b := Random(K);

> time for i := 1 to 10^7 do

time|for> c:=a*b;

time|for> end for;

Time: 3.550

> E := EllipticCurve([a,b]);

> P := Random(E);

> time for i := 1 to 10^3 do

time|for> Q := (2^256-1)*P;

time|for> end for;

Time: 1.710

Note: maybe one should first replace the classical affine Weierstrass formulas (with inversion) in`EllipticCurvePoint_field._add_`in file`schemes/elliptic_curves/ell_point.py`around line 644 by inversion-free formulas (if possible). - Luca de Feo proposes to implement other models of elliptic curves (Edwards, Jacobi, Hessian, ...)
- [suggested by Paul Zimmermann]
a topic not directly related to elliptic and hyperelliptic curve
cryptography is the discrete logarithm in finite fields, which is
inefficient in Sage. The following example is taken from the book
Calcul mathématique avec
Sage (in french):
`sage: p=10^20+39`

sage: a=mod(17,p)

sage: time r=a.log(3)

Time: CPU 20.57 s, Wall: 21.83 s - in file
`structure/coerce_actions.pyx`, function`fast_mul`at line 505 implements the right-to-left binary exponentiation, whereas the left-to-right algorithm is better. [Marion Videau and Pizzirani are working on this] - [problem reported by Thorsten Kleinjung] improve the reading of large integers from files : #11740
- Jean-Pierre Flori proposes to work on interfaces for software tools on multiprecision.org, namely MPC (arbitrary precision complex numbers), MPFRCX (univariate polynomials over arbitrary precision real or complex numbers) and CM (construction of ring class fields of imaginary quadratic number fields and of elliptic curves with complex multiplication via floating point approximations). Note that there already exists an optional package for MPC, see ticket 4446 [Jean-Pierre Flori works on this, see http://www.infres.enst.fr/~flori/ecc2011/], #11805 (MPC), #11806 (MPFRCX), #11807 (CM).
- Jean-Pierre Flori proposes to implement other methods to compute the Hilbert polynomial, and methods to construct ordinary curves with prescribed embedding degrees. Maybe a few things can be reused from the PBC library.
- some work on pairings, see for example ticket #10912 (already in Sage 4.7.1)
- a Pairing Based Signature Scheme : #11803
- Luca De Feo proposes to work on isogenies and modular polynomials
- Pierrick Gaudry works on a random function for hyperelliptic curves and their Jacobian

- the algorithm for computing Lucas sequences modulo
`n`in A.2.4 is not implemented in Sage. What is implemented in`sage.rings.finite_rings.integer_mod`is a routine`fast_lucas`which computes the (plain) Lucas numbers, but only for Q=1. [Ramanna, Singh and Venkatesh are working on this, see #11802]

You can also work on some tickets needing review: 10057, 10850, 10973 (complex), 9320, 9411, 10843, 8241, 8558, 9408, 9887, 10112, 10255, 11455, 11475, 11554, 11630, 11685, 11780, 1145, 11593, 11770, 11781, 7695, 11698

You can also work on tickets for Sage 4.7.2 related to elliptic curves