CADO NFS Usage Notes

Given the dearth of discrete logarithm implementations currently available on the internet, we thought it plausible to explore the possibility of applying number field sieve implementations to solving the discrete logarithm problem (after all, its use is common to both factoring and discrete logarithm calculations). A brief Google turned up the CADO NFS implementation of the general number field sieve along with some impressive factoring results.

In researching the applicability of the number field sieve to the discrete logarithm problem, we have found the following references to be useful:

• CADO-NFS: An Implementation of The Number Field Sieve
• The impact of the number field sieve on the discrete logarithm problem in finite fields by O.Schirokauer
• On the computation of discrete logarithms in finite prime fields by D.Weber
• Algebraic Number Theory by T.Weston
• The Development of the Number Field Sieve edited by A.Lenstra and H.Lenstra
• Algorithmic Cryptanalysis by A.Joux.

Note:

• these are ongoing experiments!
• in phase 1, with only 12 cores, we were able to sieve a suitably sized set of relations in 6-7 hours (a significant speed up compared to gdlog!)

Phase 1: Sieving

TODO:

Phase 2: Building the Logbase

TODO:

Phase 3: Calculating a Discrete Logarithm

TODO: