CADO-NFS and the Number Field Sieve to compute discrete logarithms in finite fields
Polynomial Selection for NFS-DL in non-prime finite fields
I contribute to the polynomial selection for large characteristic non-prime fields. For the moment, the polynomial selection for quadratic extensions of large prime fields with the Conjugation method is available. The polynomial selection for cubic, quartic and sextic fields is under development, at the state of a magma prototype.
Individual Discrete Logarithms in non-prime finite fields
The code of the paper
- 2015. Computing Individual Discrete Logarithms Faster in GF(p^n) with the NFS-DL algorithm. Aurore Guillevic. Asiacrypt 2015, Auckland, New Zealand, November 29-December 3, 2015, LNCS, Part I, volume 9452, pages 149-173. HAL:01157378
is also under development, at a Magma stage for the moment. A C/C++ cado-nfs version is planed for the end of 2017.
I am usually contacted by researchers who would like to use the source code I developed in my thesis, to compare the efficiency of pairings over prime order groups and over composite-order groups. This comparison was discussed in the paper
- Comparing the Pairing Efficiency over Composite-Order and Prime-Order Elliptic Curves. Aurore Guillevic. ACNS 2013, Banff, Alberta, Canada, LNCS 7954, pp. 357-372. eprint 2013:218
and for a more recent version, see the section 3.3 of my thesis available here.
Unfortunately for confidentiality reasons the source code is not available but here are alternative libraries to efficiently compute pairings over elliptic curves.
- the RELIC library (in C++) of Diego Aranha and C.P.L Gouvea
- the MIRACL library of M. Scott, in C/C++.
These two above libraries are the fastest ones as far as I know. Please feel free to contact me if you have better suggestions.
Here is another one I heard about:
- the TEPLA library of the Tsukuba University.
If you prefer a more user-friendly version, here are other implementations.
- the PARI/GP has a Tate pairing implementation. PARI is known to be fast, but maybe it is not optimized specifically for pairings.
- Magma comes with an implementation of Tate pairings, Weil pairings, and Ate parings. Magma is a non-free software but maybe your university or institute has a license for it.
- I’m not very familiar with SageMath but there should be a pairing implementation coming with it, maybe this is the PARI-GP one.