Clone wiki

Challenge11 / cado

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:


  • 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


Phase 2: Building the Logbase


Phase 3: Calculating a Discrete Logarithm