ECDLP Solver

This ECDLP solver is the result of some months spent in reading, thinking and creating. My aim was/is to write the fastest ECDLP solver for any field. To achieve this, I extend some old ideas with my new ones and add modern techniques for multi-core systems and 64bit processors. More detailed tests are still to come, but currently the solver is 2-30 times faster than other implementations.

UNDER THE HOOD

• Assembler/ C code
• Pohlig-Hellman algorithm
• Parallel Pollard Rho algorithm “Parallel Collision Search with Cryptanalytic Applications” written by Paul C. van Oorschot and Michael J. Wiener
• My inverse elimination algorithm
• Multi-core system support
• X86-64 system support
• Ability to stop and continue
• Large-scale parallelization support

INPUT THE TASK

Start the solver with the job.txt in command line.

Sample job.txt:

GF := GF(954101701339883); <-modulus (p) E := EllipticCurve([GF|3107,3099]); <-curve parameters (a,b) G := E![795426908202550,542650698718897]; <-Base (G) K := E![377896003719876,438402788328087]; <-Argument (K) / <-Here starts the factorization of the order (n) FactorCount:=6; <-number of factors 2; <-Factor1 2; <-Factor2... 2; 2; 7; 8518765159951; / <-End of the job file

Feel free to look at the example jobs and modify the job_template.txt.

STOP AND CONTINUE

When you run the solver, it creates a .rho.dat file in the same directory if it doesn’t exist. This intermediate file contains the current progress of the solver, and if you close the solver, the progress is safe. Once a solution is found and the solver is closed, the intermediate file contains all needed information for the solver, to get the result instantly.

LARGE-SCALE PARALLELIZATION

If you have multiple separated systems and a job file, just copy it and run the solver on each system, so you will have multiple .rho.dat intermediate files.

Once in a while (when you think, that enough iterations were made) you have to stop each solver and copy the content of .rho.dat files into one big .rho.dat file (just append the content).

Run one solver, so it can read the big .rho.dat file. If a result appears after the reading, you’re done, otherwise run the solver instances again and delete the old .rho.dat files, but keep the big one.

After a while you can append the new .rho.dat files to the old big .rho.dat file and run one solver instance again to check the results.