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));
  > 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
  Challenge: beat Magma on that example!
  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

Topics related to Annex A of the IEEE P1363.3/D2 Draft Standard for Identity-based Public-key Cryptography Using Pairings

• 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